首页 > 代码库 > BZOJ 1150 [CTSC2007]数据备份Backup（贪心+优先队列）
BZOJ 1150 [CTSC2007]数据备份Backup（贪心+优先队列）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1150
【题目大意】
给出n个数，请你挑出k对（每个数不可重复选取），使得他们差的绝对值之和最小（k小于等于n/2)
【题解】
因为数列给出有序，省去排序步骤，我们发现最优答案一定是选择k对相邻的数，
因此我们将相邻的数两两之间求差，得到差分数列，
现在问题转化为在这个新的数列中，选取k个不相邻的数，使得和最小。
我们发现在选取一个数之后，只对左右两边的数有影响，
所以，每当我们选取一个数，就把这个数以及它两边的数删除，
然后再在它的位置上新加一个数，值为被选取的数两边数的和减去被选去的数
那么我们如果选了这个数，就相当于原来的数我们就不选了，类似于最大流的退流思想。
这样做之后，我们每次只要选择最小的数，累加到答案即可。
对于被删除了却仍然在优先队列中的数，我们用一个标记来维护它。
【代码】
#include <cstdio>#include <algorithm>#include <queue>#include <cstring>using namespace std;const int N=200010;unsigned long long ans;bool del[N];struct data{ int id,key,l,r; bool operator <(const data&rhs)const{ return key>rhs.key; }}w[N];priority_queue<data> Q;int a[N],n,k;int main(){ while(~scanf("%d%d",&n,&k)){ ans=0; memset(del,0,sizeof(del)); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<n;i++){ w[i].id=i; w[i].key=a[i+1]-a[i]; w[i].l=i-1; w[i].r=i+1; Q.push(w[i]); }n--; w[n].r=w[0].l=w[0].r=0; w[0].key=0x3f3f3f3f; while(k--){ for(;;){ data t=Q.top(); Q.pop(); int id=t.id,l=w[id].l,r=w[id].r; if(del[id])continue; del[id]=del[l]=del[r]=1; ans+=w[id].key; w[++n].id=n; w[n].key=w[l].key+w[r].key-w[id].key; w[n].l=w[l].l; w[n].r=w[r].r; w[w[l].l].r=n; w[w[r].r].l=n; Q.push(w[n]); break; } }printf("%lld\n",ans); }return 0;}BZOJ 1150 [CTSC2007]数据备份Backup（贪心+优先队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。