[BZOJ1150][CTSC]数据备份Backup

首先肯定要选择相邻的公司配对才会距离最小 先把两两之间的距离加入小根堆中 每次取出堆顶，加入答案，删掉左右线段，再扔进去len[l]+len[r]-len[now] 这样如果这个新点被取到，说明取两边而不取中间 做K次，贪心就是正确的了

/**************************************************************Problem: 1150User: momokaLanguage: C++Result: AcceptedTime:620 msMemory:6000 kb****************************************************************/#include<cstdio>#include<cstring>#include<queue>#include<vector>#include<algorithm>#define rep(i,s,t) for(int i=s;i<=t;++i)#define drep(i,t,s) for(int i=t;i>=s;--i)#define inf 0x3f3f3f3fusing namespace std;long long ans,val[150010];int l[150010],r[150010],id,n,k,d[100001];typedef pair<long long,int>ele;priority_queue<ele,vector<ele>,greater<ele> >q;bool mark[150010];inline int read(){char ch=getchar();int f=1,x=0;while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*f;}int main(){n=read(); k=read();rep(i,1,n) d[i]=read();rep(i,1,n-1){val[++id]=d[i+1]-d[i];q.push(make_pair(val[id],id));l[id]=id-1;r[id]=id+1;}r[0]=1; val[0]=1LL<<61; //q.push(make_pair(val[0],0));l[id+1]=id; val[id+1]=1LL<<61; // q.push(make_pair(val[id+1],id+1));++id;rep(i,1,k){while (mark[q.top().second]) q.pop();ele now=q.top();q.pop();int idn=now.second;ans+=now.first;int ls=l[idn],rs=r[idn];mark[ls]=1;mark[rs]=1;l[idn]=l[ls]; r[l[idn]]=idn;r[idn]=r[rs]; l[r[idn]]=idn;val[idn]=val[ls]+val[rs]-now.first;q.push(make_pair(val[idn],idn));}printf("%lld\n",ans);return 0;}