BZOJ 2288: 【POJ Challenge】生日礼物贪心，堆 BZOJ 1150强化

2019-11-08 02:55:59

字体：大中小

来源：转载

供稿：网友

题意：给出一个长度为n的数列，要求从中取出不超过m段连续的数，使其和最大。 n<=100000

解题方法：这题可以把一段同号的数并成一个数，那么就变成了一个正负交替的序列，然后把头尾的负数去掉。有一种想法就是把所有的正值都加起来，然后把所有数的绝对值加进优先队列，每次去一个最小的出来然后减掉，最后的即为答案。为什么是正确的呢？因为如果减去的值在原数列中为正则相当于不要这个数，否则就相当于选了这个负数然后把两边的正值合并起来。但有一个问题，就是若选了一个数那么其两边的数就必定不能被选，那么就转换成了数据备份了。题解参考的hzwer大牛的，orz

//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, v; node(){} node(int pos, int v) : pos(pos), v(v) {} bool Operator < (const node &rhs) const{ return v > rhs.v; }};PRiority_queue <node> que;int n, m, a[maxn], b[maxn], L[maxn], R[maxn], vis[maxn];int main(){ n = read(); m = read(); for(int i = 1; i <= n; i++) b[i] = read(); int n1 = 1; a[1] = b[1]; for(int i = 2; i <= n; i++){ if(a[n1] <= 0 && b[i] <= 0) a[n1] += b[i]; else if(a[n1] >= 0 && b[i] >= 0) a[n1] += b[i]; else a[++n1] = b[i]; } if(a[n1] <= 0) n1--; if(a[1] <= 0){ for(int i = 1; i < n1; i++){ a[i] = a[i+1]; } n1--; } n = n1; int cnt = 0, ans = 0; for(int i = 1; i <= n; i++){ if(a[i] > 0){ cnt++; ans += a[i]; } que.push(node(i, abs(a[i]))); a[i] = abs(a[i]); L[i] = i - 1; R[i] = i + 1; } R[n] = L[1] = 0; if(cnt <= m){ printf("%d/n", ans); return 0; } m = cnt - m; for(int i = 1; i <= m; i++){ node now = que.top(); que.pop(); while(vis[now.pos] && !que.empty()) {now = que.top(); que.pop();} if(vis[now.pos]) break; ans -= now.v; if(que.empty()) break; int x = now.pos; if(!R[x]){ vis[x] = 1; vis[L[x]] = 1; R[L[L[x]]] = 0; } else if(!L[x]){ vis[x] = 1; vis[R[x]] = 1; L[R[R[x]]] = 0; } else{ node nxt; vis[L[x]] = vis[R[x]] = 1; nxt.v = a[x] = a[R[x]] + a[L[x]] - a[x]; nxt.pos = x; que.push(nxt); if(R[R[x]]) L[R[R[x]]] = x; if(L[L[x]]) R[L[L[x]]] = x; L[x] = L[L[x]]; R[x] = R[R[x]]; } } printf("%d/n", ans); return 0;}

上一篇：在SpringBoot中访问静态资源

下一篇：Kruskal