首页 > 代码库 > [CTSC2007][APIO2007]数据备份Backup
[CTSC2007][APIO2007]数据备份Backup
题目：BZOJ1150、codevs1615、洛谷P3620
题目大意：有n个点，k条链，每个点离原点有一定的距离。要你用k条链连接2k个点，使得k条链的长度最短。
解题思路：毕竟是CTSC级别的题目，很难找出正确算法。在网上翻阅了很多资料后，终于理解了此题的正确算法。orz
正确算法为：贪心+链表+堆。
首先每次肯定是链相邻的2个点，所以我们先把相邻2个点的差值求出来，得到有n-1个数的数列。
然后问题就变成“在这个数列中寻找k个互不相邻的点，使得它们的和最小”。
我们把所有的数扔进一个堆里，每次贪心找出最小的数，在答案里把它加上。
这时就会出现一个问题：假设我们贪心出了第i个数，那么有可能选第i-1个数和第i+1个数最终的结果优于选第i个数。
所以我们每次贪心时，把找到的那个数的前一个数和后一个数删掉，把“前一个数+后一个数-原数”的值扔进堆里，如果这个数被选，相当于选了前一个数和后一个数而不选原数。
而链表记录的是每个数的前一个和后一个。详见代码第32~35行。
在删数时，并不需要在堆里找到这个数，只需把它的值改为inf就行了。详见代码第36行。
C++ Code：
#include<cstdio>#include<ext/pb_ds/priority_queue.hpp>const int inf=int(1000000000*1.3);using namespace std;struct shuju{ int dis,num; shuju(int d,int n):dis(d),num(n){} bool operator<(const shuju& rhs)const{return dis>rhs.dis;}};__gnu_pbds::priority_queue<shuju,less<shuju>,__gnu_pbds::pairing_heap_tag>h;int n,k,dis[100005],pre[100005],nxt[100005];int main(){ scanf("%d%d",&n,&k); int x,y; scanf("%d",&x); for(int i=2;i<=n;i++){ scanf("%d",&y); dis[i]=y-x;x=y; h.push(shuju(dis[i],i)); pre[i]=i-1;nxt[i]=i+1; } int ans=0; pre[2]=nxt[n]=0; while(k--){ while(h.top().dis!=dis[h.top().num])h.pop(); int k=h.top().num; int l=pre[k],r=nxt[k]; h.pop(); ans+=dis[k]; if(l&&r)dis[k]=dis[l]+dis[r]-dis[k];else dis[k]=inf; pre[nxt[r]]=k; nxt[pre[l]]=k; nxt[k]=nxt[r]; pre[k]=pre[l]; dis[l]=dis[r]=inf; h.push(shuju(dis[k],k)); } printf("%d\n",ans); return 0;}
[CTSC2007][APIO2007]数据备份Backup
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。