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（贪心+优先队列）

最新文章

热门文章