題目鏈接：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;}新聞熱點
疑難解答
