首页 > 代码库 > [CTSC2007]数据备份Backup 题解

[CTSC2007]数据备份Backup 题解

2024-10-27 11:03:02   211人阅读

题意：

　　一维直线上有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 题解


联系
我们