首页 > 代码库 > [CTSC2007]数据备份Backup 题解
[CTSC2007]数据备份Backup 题解
题意:
一维直线上有n个点,任取2k个互不相同的点组成k条链,求链的最小总长
思路:
1.最优时链不相交,相邻两两相减,将题目转化为:在n-1个数中取互不相邻的k个数使总和最小。
2.贪心取最小的“数”(设为a[x])累加(表示已经取了),再建立一个“反悔机制”(可能和网络流相似):将a[x]向两边各拓展一个,合并成为新的“数”,其值为两边之和减去a[x](取这段则可以等同不取a[x]而取其它),再将a[x]和其两边的删掉。这样可以保证最优,同时也可保证取的数不相邻(未被删去的段的两端都没有被取到)
3.用堆维护最小值,用双向链表实现向两边拓展。注意边界:当某一a[x]的一端无法拓展时,则显然拓展不如当前优,将可拓展的一端删去,防止被取相邻两个数。
反思:
堆的基本操作不是很熟悉,同时用编号映射有点绕。
代码:
1 #include<cstdio> 2 const int M=100010; 3 #define swap(x,y) o=x,x=y,y=o 4 int n,m,t,o,sum,a[M],id[M],di[M],pre[M],nex[M]; 5 //堆中第i个点在读入时的编号为id[i] 读入时的第i个点在堆中的编号为di[i] 6 //pre[] nex[]中存的是读入时的编号读入时的编号,下标也为读入时的编号 7 8 void up(int x) 9 { 10 for (;a[id[x]]<a[id[x>>1]] && x>1;x=x>>1) 11 swap(di[id[x]],di[id[x>>1]]),swap(id[x],id[x>>1]); 12 } 13 14 void down(int x) 15 { 16 for (int y=x<<1;y<=t;) 17 { 18 if (y<t && a[id[y]]>a[id[y|1]]) ++y; 19 if (a[id[x]]>a[id[y]]) 20 swap(di[id[x]],di[id[y]]),swap(id[x],id[y]),x=y,y=x<<1; 21 else break; 22 } 23 } 24 25 void add(int x) { id[++t]=x,up(di[x]=t); } 26 void del(int x) { id[di[x]]=id[t],up(di[id[t--]]=di[x]),down(di[x]); } 27 28 int read() 29 { 30 int x=0; char ch=getchar(); 31 while (ch<48 || ch>57) ch=getchar(); 32 while (ch>47 && ch<58) x=(x<<1)+(x<<3)+ch-48,ch=getchar(); 33 return x; 34 } 35 36 int main() 37 { 38 int n=read(),m=read(),i,x; 39 for (i=1;i<=n;++i) a[i]=read(); 40 for (i=1;i<n;++i) a[i]=a[i+1]-a[i],pre[i]=i-1,nex[i]=i+1,add(i); 41 for (;m--;) 42 { 43 sum=sum+a[x=id[1]]; 44 if (!pre[x] && nex[x]==n) break; 45 del(x); 46 if (!pre[x]) del(nex[x]),pre[nex[nex[x]]]=0; 47 else if (nex[x]==n) del(pre[x]),nex[pre[pre[x]]]=n; 48 else 49 { 50 del(pre[x]),del(nex[x]);; 51 a[x]=a[pre[x]]+a[nex[x]]-a[x],add(x); 52 nex[pre[x]=pre[pre[x]]]=pre[nex[x]=nex[nex[x]]]=x; 53 } 54 } 55 printf("%d\n",sum); 56 return 0; 57 }
[CTSC2007]数据备份Backup 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。