BZOJ 1150 数据备份Backup 【贪心】【堆】

2019-11-08 02:54:49

字体：大中小

来源：转载

供稿：网友

题目链接：http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1150

题意：就是问你求完差分后选出 k 个数，使得他们的和最小。题解： TMD这道题搞得我快要神志不清了。。WA了12次才搞出来。。这道题基本就是SB贪心，用一个堆维护就可以了。但是一定要注意细节。。我快要被坑惨了。。

代码：

#include <queue>#include <cstdio>#include <vector>using namespace std;const int size = 300005, inf = 1 << 29;int n, k;#define pii pair<int, int>int a[size];int pre[size], nxt[size];priority_queue<pii, vector<pii>, greater<pii> > que;int main() { scanf("%d %d", &n, &k); int t1 = 0, t2; for ( int i = 1; i <= n; i ++ ){ scanf("%d", &t2); a[i] = t2-t1; pre[i] = i-1; nxt[i] = i+1; t1 = t2; } int ans = 0; for ( int i = 2; i <= n; i ++ ) que.push(make_pair(a[i], i)); pre[2] = 0; nxt[n] = 0; for ( int i = 1; i <= k; i ++ ) { while(que.top().first != a[que.top().second]) que.pop(); int x = que.top().second; int left = pre[x], right = nxt[x]; ans += a[x]; que.pop(); pre[nxt[x] = nxt[right]] = x; nxt[pre[x] = pre[left]] = x; a[x] = left&&right?min(inf, a[left]+a[right]-a[x]):inf; a[left] = a[right] = inf; que.push(make_pair(a[x], x)); } printf("%d/n", ans); return 0;}

上一篇：mysql求排序后前几名（包含并情况）

下一篇：【Oracle】用户和监听服务