题意： 有n栋楼排成一排，要求在k对楼之间连接电缆，每栋楼只能被连接一次，求最小的∑|dis[x]−dis[y]|.x，y分别为电缆的两个端点。n<=100000 解题方法： 显然k对电缆连接的必然都是相邻的两栋楼，那么问题可以转换成有n-1个数，a[i]=dis[i+1]-dis[i]，从中取出k个数满足其互不相邻且和最小。那么就可以用贪心来做。每次找一个最小的，假设是x，那么x+1和x-1要么不选，要么都选，那么可以把这三个数合并成一个数，权值为a[x+1]+a[x-1]-a[x]，然后把原来的三个数删掉即可。可以用优先队列和双向链表来维护。为了方便的使用PRiority_queue，直接把a[n]设为-inf就可以了。细节见代码
//bzoj 1150#include <bits/stdc++.h>using namespace std;const int inf = 0x7fffffff;const int maxn = 100010;typedef long long LL;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;}inline LL llread(){ char ch=getchar(); LL 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;}struct node{ int pos; LL v; node(){} node(int pos, LL v) : pos(pos), v(v) {} bool Operator < (const node &rhs) const{ return v < rhs.v; }};priority_queue <node> que;int n, m, L[maxn], R[maxn], vis[maxn];LL a[maxn], dis[maxn];int main(){ n = read(); m = read(); while(!que.empty()) que.pop(); for(int i = 1; i <= n; i++) dis[i] = llread(); for(int i = 1; i <= n; i++){ if(i < n) a[i] = dis[i] - dis[i + 1]; else a[i] = -inf; node u; u.v = a[i]; u.pos = i; que.push(u); R[i] = i + 1; L[i] = i - 1; } R[n] = 1; L[1] = n; LL ans = 0; for(int i = 1; i <= m; i++){ node now = que.top(); que.pop(); while(vis[now.pos] && !que.empty()){now = que.top(); que.pop();} ans -= now.v; int x = now.pos; node v; v.pos = x; v.v = a[x] = 1LL * (a[R[x]] + a[L[x]] - a[x]); que.push(v); R[L[L[x]]] = x; L[R[R[x]]] = x; vis[L[x]] = 1; vis[R[x]] = 1; R[x] = R[R[x]]; L[x] = L[L[x]]; } printf("%lld/n", ans); return 0;}新闻热点
疑难解答
