CodeVs 1615 数据备份

题目：数据备份

链接：Here

题意：有n个点在一条线上，每次连线可以连接两个点（每个点只能被连一次），要求找出m个连线，他们的和最小（连线权值就是两点距离），输出最小的和。给出n、m和每个点的坐标。

思路：

　　可反悔贪心。

　　容易得出连线必然是选择相邻的点组成，那么从连线权值最小的开始选（用优先队列实现），假设现在有6个连线（1、2、3、4、5、6），如果第一次选了3，但后面有可能发现w[3] + w[x]（后面找到的一个满足条件的权值最小的连线）> w[2] + w[4]（正常情况下选了3，就不可以选择2、4了），那么我可以反悔，重新选择2、4而抛弃3，要想做到这样，在把w[3]算入总和时，得把w[2]+w[4]-w[3]放入优先队列，以供日后反悔，基于假设，w[2]+w[4]-w[3]<w[x]，那么先出来的就是w[2]+w[4]-w[3]，此时sum+w[2]+w[4]-w[3]和最初选了2、4的结果一致，当然，在把w[2]+w[4]-w[3]算入总和时，得把这一块的左边连线w[1]与右边连线w[5]再结合，也就是w[1]+w[5]-(w[2]+w[4]-w[3])，放入优先队列，以供后面可以反悔。容易得到这个贪心是正确的。

AC代码:

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 #include<math.h>

 #include<set>

 #include<map>

 #include<list>

 #include<stack>

 #include<queue>

 #include<vector>

 #include<string>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define lson rt<<1

 #define rson rt<<1|1

 #define N 100010

 #define M 100010

 #define Mod 1000000007

 #define LL long long

 #define INF 1000000007

 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)

 #define For(i,f_start,f_end) for(int i=f_start;i<f_end;i++)

 #define REP(i,f_end,f_start) for(int i=f_end;i>=f_start;i--)

 #define Rep(i,f_end,f_start) for(int i=f_end;i>f_start;i--)

 #define MT(x,i) memset(x,i,sizeof(x))

 #define gcd(x,y) __gcd(x,y)

 const double PI = acos(-);

 struct Node

 {

   int w,l,r,pos;

   bool friend operator < (Node a,Node b)

   {

     return a.w>b.w;

   }

 }w[N];

 bool vis[N];

 priority_queue<Node> q;

 int main()

 {

   int n,k;

   scanf("%d%d",&n,&k);{

     int pre = ;

     FOR(i,,n){

       scanf("%d",&w[i].w);

       int tmp = w[i].w;

       w[i].w -= pre;

       pre = tmp;

       w[i].pos = i;

       w[i].l = i-;

       w[i].r = i+;

     }

     w[].l = w[n].r = ;

     //while(q.size()) q.pop();

     FOR(i,,n){

       q.push(w[i]);

     }

     int sum = ;

     FOR(i,,k){

       Node tmp;

       while(q.size()){

         tmp = q.top();

         q.pop();

         if(tmp.w == w[tmp.pos].w) break;

       }

       //printf("%d %d %d %d\n",tmp.l,tmp.r,tmp.pos,tmp.w);

       tmp = w[tmp.pos];

       sum += tmp.w;

       Node now;

       now.pos = tmp.pos;

       now.l = w[tmp.l].l;

       now.r = w[tmp.r].r;

       w[now.l].r=now.pos;

       w[now.r].l=now.pos;

       if(tmp.l== || tmp.r==) now.w=INF;

       else now.w = w[tmp.l].w + w[tmp.r].w - tmp.w;

       w[now.pos]=now;

       //printf("===%d %d %d %d\n",now.l,now.r,now.pos,now.w);

       w[tmp.l].w = INF;

       w[tmp.r].w = INF;

       q.push(now);

     }

     printf("%d\n",sum);

   }

   return ;

 }