首页 > 代码库 > bzoj1150[CTSC2007]数据备份Backup
bzoj1150[CTSC2007]数据备份Backup
bzoj1150[CTSC2007]数据备份Backup
题意：
n个地方，在其中找k对地方，每个地方只属于一对。定义一对的费用为两个地方的距离，求最小费用总和。
题解：
把所有相邻地方距离放入一个集合中，每次取出最小的那个距离x，然后将相邻两边的距离l，r合并成l+r-x。如果这个x缺一边相邻，则将剩下那一边的距离去掉，如果缺两边相邻，则不用去掉。这个找相邻的过程用链表维护，同时找最小距离以及删距离的操作用set维护（好像也可以用手写堆，然而我不会）。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <set> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 100010 7 using namespace std; 8 9 inline int read(){10 char ch=getchar(); int f=1,x=0;11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}12 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();13 return f*x;14 }15 int n,k,a[maxn]; long long ans;16 struct sn{17 int pos,v;18 bool operator < (const sn &x)const{return v!=x.v?v<x.v:pos<x.pos;}19 };20 set<sn>s;21 struct nd{int v,l,r;}; nd nds[maxn];22 int main(){23 n=read(); k=read(); int st=read(); inc(i,1,n-1){int x=read(); a[i]=x-st; st=x;} n--;24 inc(i,1,n){s.insert((sn){i,a[i]}); nds[i]=(nd){a[i],i-1,i+1>n?0:i+1};}25 inc(i,1,k){26 set<sn>::iterator xx=s.begin(); int x=xx->pos; ans+=xx->v; s.erase(xx);27 if(!nds[x].l&&!nds[x].r)continue;28 else if(!nds[x].r){29 xx=s.find((sn){nds[x].l,nds[nds[x].l].v}); s.erase(xx); nds[nds[nds[x].l].l].r=0;30 }else if(!nds[x].l){31 xx=s.find((sn){nds[x].r,nds[nds[x].r].v}); s.erase(xx); nds[nds[nds[x].r].r].l=0;32 }else{33 nds[x].v=nds[nds[x].l].v+nds[nds[x].r].v-nds[x].v;34 xx=s.find((sn){nds[x].l,nds[nds[x].l].v}); s.erase(xx);35 xx=s.find((sn){nds[x].r,nds[nds[x].r].v}); s.erase(xx);36 s.insert((sn){x,nds[x].v});37 nds[x].l=nds[nds[x].l].l; nds[x].r=nds[nds[x].r].r; nds[nds[x].l].r=x; nds[nds[x].r].l=x;38 }39 }40 printf("%lld",ans); return 0;41 }
20160902
bzoj1150[CTSC2007]数据备份Backup
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。