CF460CPresent（二分答案 线段树）题解
思路
显然，这题正着不太好推，那么就考虑二分答案，有一个很大的问题，我们需要在\(O(n\log n)\)或者\(O(n)\)的时间内判断我们二分答案的可行性。首先肯定想到贪心，但是你会发现每一个元素需要加的值不一样，加了值以后影响的范围也不一样，并不好维护。
因为涉及到区间修改，考虑使用线段树。我们维护每一位置已经加了多少。
首先明确什么情况下是必须操作一次的（当前值小于二分所得的最小值的前提下）：
当前节点已经加的值小于需要加的值
而对于每一次操作，我们可以用线段树方便地进行区间加。至于每一个点已经加的值，单点查询就可以了。
代码
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn = 1e5 10;int n,m,w,a[maxn];struct Seg_Tree{ #define lc(x) x << 1 #define rc(x) x << 1 | 1 int c[maxn << 2],tag[maxn << 2]; void clear(){ memset(c,0,sizeof(c)); memset(tag,0,sizeof(tag)); } void f(int l, int r, int p, int x){ c[p] = (r - l 1) * x; tag[p] = x; } void downdate(int l, int r, int p){ if(tag[p]){ int mid = (l r) >> 1; f(l, mid, lc(p), tag[p]); f(mid 1, r, rc(p), tag[p]); tag[p] = 0; } } void add(int L, int R, int l, int r, int p, int x){ if(L <= l && R >= r){ f(l, r, p, x); return; } downdate(l, r, p); int mid = (l r) >> 1; if(mid >= L) add(L, R, l, mid, lc(p), x); if(mid < R) add(L, R, mid 1, r, rc(p), x); c[p] = c[lc(p)] c[rc(p)]; } int query(int l, int r, int p, int pos){ if(l == r) return c[p]; downdate(l, r, p); int mid = (l r) >> 1; if(mid >= pos) return query(l, mid, lc(p), pos); else return query(mid 1, r, rc(p), pos); }}tree;inline int check(int mid){ int cnt = 0, flag = 1; tree.clear(); //记得清空 for(int i = 1; i <= n; i){ if(a[i] < mid){ int val = tree.query(1, n, 1, i); if(val < mid - a[i]){ cnt = mid - a[i] - val; tree.add(i, i w - 1, 1, n, 1, mid - a[i] - val); } } if(cnt > m){flag = 0; break;} } if(cnt > m || !flag) return 0; else return 1;}int main(){ int h = 0x3f3f3f3f, l = 0x3f3f3f3f, mid; //这里h不能设成1e9 10，因为答案可能会大于它 scanf("%d%d%d", &n, &m, &w); for(int i = 1; i <= n; i){ scanf("%d", a i); l = min(l, a[i]); } while(h >= l){ mid = (h l) >> 1; if(!check(mid)) h = mid - 1; else l = mid 1; } printf("%d\n", l - 1); return 0;}
赞 (0)