分析：差分数组A求出相邻两个的差，则问题转化为了：在差分数组A中找k个数，满足k个数之和最小且互不相邻.建立一个小根堆把N-1个点都丢进去。有性质：要么选最小值，要么选最小值旁边两个值。因此先选出最小值的点A[i]，用权值为A[i-1]+A[i+1]-A[i]的一个点代替掉原先的这三个点丢进堆即可.
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=100005;
int a[N],b[N],l[N],r[N],visit[N];
struct node{
int num,val;
bool operator <(const node &x)const{
return val>x.val;
}
}temp;
priority_queue<node>q;
int main(){
int n=read(),k=read();
for(int i=1;i<=n;++i)b[i]=read();
for(int i=1;i<=n-1;++i)a[i]=b[i+1]-b[i];
a[0]=1e9;a[n]=1e9;
for(int i=1;i<=n-1;++i){
temp.num=i;temp.val=a[i];
l[i]=i-1;r[i]=i+1;
q.push(temp);
}
r[0]=1;l[n]=n-1;
int ans=0;
while(k--){
while(visit[q.top().num])q.pop();
temp=q.top();q.pop();
int u=temp.num,v=temp.val;ans+=v;
a[u]=a[l[u]]+a[r[u]]-a[u];temp.val=a[u];
visit[l[u]]=1;visit[r[u]]=1;
l[u]=l[l[u]];r[l[u]]=u;
r[u]=r[r[u]];l[r[u]]=u;
q.push(temp);
}
printf("%d
",ans);
return 0;
}
洛咕良心搞了个四倍经验.SP1553多组数据版 记得清空队列和visit数组就好了，代码就不给了.
种树上面是求最小值，这里只求最大值，所以小根堆变成大根堆即可，代码也不给了.
[国家集训队]种树线性变环形，给一下代码吧，差别也不太大.
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=200005;
int a[N],l[N],r[N],visit[N];
struct node{
int num,val;
bool operator <(const node &x)const{
return val<x.val;
}
}temp;
priority_queue<node>q;
int main(){
int n=read(),k=read();if(k>n/2){puts("Error!");return 0;}
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i){
temp.num=i;temp.val=a[i];
l[i]=i-1;r[i]=i+1;
q.push(temp);
}
l[1]=n;r[n]=1;//差别在这里，保证环形存在
int ans=0;
while(k--){
while(visit[q.top().num])q.pop();
temp=q.top();q.pop();
int u=temp.num,v=temp.val;ans+=v;
a[u]=a[l[u]]+a[r[u]]-a[u];temp.val=a[u];
visit[l[u]]=1;visit[r[u]]=1;
l[u]=l[l[u]];r[l[u]]=u;
r[u]=r[r[u]];l[r[u]]=u;
q.push(temp);
}
printf("%d
",ans);
return 0;
}