题目大意:将k对点两两相连,求最小长度
易证得,最优方案中,相连的办公楼一定是取相邻的比取不相邻的要更优
然后就可以用贪心来做这道题了。。
之前向CZL大神学习了用堆来贪心的做法orz
大概思路就是将初始所有的线段放进堆里
每次取最短的线段进行连接,且ans+=a[i]
取完后删除当前线段,与相邻的两条线段,同时再插入新边,权值为a[pre]+a[next]-a[now]
其作用与最大流中的反向弧有点像,下一次若取到这条边,即ans+=a[pre]+a[next]-a[now]
很明显a[now]与之前抵消了,即不取now,反而取相邻的两条边去了
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; *; struct node{ int id; }; priority_queue<node> Q; int pre[maxn],next[maxn],k,a[maxn],n; bool del[maxn]; int tot,last,now,ans; bool operator<(node x, node y){ return a[x.id]>a[y.id]; } int main(){ scanf("%d%d", &n, &k); scanf("%d", &last); tot=; ; i<n; i++){ scanf("%d", &now); a[++tot]=now-last; last=now; } ; i<n; i++){ Q.push((node){i}); pre[i]=i-; next[i]=i+; } pre[]=next[tot]=; a[]=; // Attention:不能是maxlongint,因为后面a[++tot]会爆 while (k--){ while (!Q.empty() && del[Q.top().id]) Q.pop(); if (Q.empty()) break; int now=Q.top().id; ans+=a[now]; Q.pop(); int l=pre[now],r=next[now]; del[now]=del[l]=del[r]=; a[++tot]=a[l]+a[r]-a[now]; Q.push((node){tot}); pre[tot]=pre[l]; next[tot]=next[r]; if (pre[tot]) next[pre[tot]]=tot; if (next[tot]) pre[next[tot]]=tot; } printf("%d\n", ans); ; }