cs集训营：[CSPS牛客集训营2 T1]服务器问题

题目描述

小多计划在接下来的n天里租用一些服务器，所有的服务器都是相同的。接下来n天中，第i天需要 a i a_i ai​台服务器工作，每台服务器只能在这n天中工作m天，这m天可以不连续。
但是计划不是一成不变的，接下来有q次修改计划（修改是永久的），每次修改某一天k的需求量 a k a_k ak​。
小多希望知道每次修改之后，最少需要多少台服务器。

输入描述:

第一行三个正整数n,m,q，分别表示计划的天数，每台服务器能工作的天数和修改次数。
随后一行n个非负整数，第i个数字 a i a_i ai​
​表示原计划第i天需要多少台服务器工作。
随后q行，每行两个正整数 p i , c i p_i,c_i pi​,ci​ ，表示把第 p i p_i pi​ 天需要的服务器数目改成 c i c_i ci​。

输出描述:

第一行输出原计划需要的最少服务器数量。
随后q行，每行输出对应的修改之后，需要的最少的服务器的数量。

样例输入输出

输入

5 3 2
1 1 1 1 1
1 2
2 3

输出

2
2
3

说明

未修改时，可以租用2台服务器，分别安排给{1,4,5}和{2,3}这些天。
当第一次修改时，第一天需要两台服务器，需求变为了2 1 1 1 1，故可以安排成{1,2,3}和{1,4,5}，满足所有的需求。
第二次修改时，第二天需要三台服务器，需求变为了2 3 1 1 1。可以安排三台服务器，每台服务器安排的日子分别为{1,2,3},{1,2,4}和{2,5}，这样可以满足所有天的需求。

刚开始看到这道题的时候没什么思路，后来题面增加了m天可不连续的时候就突然觉得这道题是不是“服务器大赛”，“铺设服务器”（借鉴noip2013，2018题目）吗？
仔细想想实则不然。不过有内味儿了。

我们先思考一个问题，不考虑修改，服务器选用的个数的最理想的最小值是多少？
因为一个服务器在同一天中只能贡献1
所以最理想的情况下最大值就是需求最大的天数。
那么既然是理想的最小值，那么就存在情况，即最大值不够大，总需求量>最大值*m这时候我们的最小租用数就是最大值 * m上取整。
然后对于修改的情况
我们很容易想到我们只需要维护一个全局最大值和一个全局和即可，全局和就很简单，把每次修改的数的原数减去再加上修改的新数值即可。
那么对于全局最大，我们写一颗线段树维护一下，最简单的那种，只需要单点修改就行了。
然后对于每次询问判断一遍最小选取值即可。

考场上自己想了一个判断方法，非常麻烦，而且只拿了15分，不过再我把我原代码中写的线段树的瞎*操作改完后发现我的思路也是可以过掉这道题的。
代码注释上虽然写有考场思路，不过我还是粘上来吧。

nd为题目中的服务器需求， num为租用服务器的最小值
用线段树维护区间最大，找出nd中最大的数xm，num一定 ≥ xm
先使 num = xm
若num * m > all 直接输出all
那么num = num + (all - num * n) / m ;
若 num * m < all ，则 ++num;（其实就是上取整）

考虑修改，如果不动最大值，或者不超过最大值，
修改all，如果all < num * m 输出num
如果 > num += (all - num * m);
如果超过最大值
将num修改成最大值，判断all与num的关系
如果修改最大值，改大了 同上
如果改小了，找出最大值，重复第一次操作
（这里操作有点多了，其实直接修改，更新一下最大值，然后判断就行，不用管这么多）

两个代码我都放一下吧
C o d e Code Code
正解思路

#include<bits/stdc++.h>#define N 1001#define MAXN 4000010#define gtc() getchar()#define ll long long#define rg registerusing namespace std;template <class T>inline void read(T &s){T w = 1, ch = gtc(); s = 0;while(!isdigit(ch)){if(ch == '-') w = -1; ch = gtc();}while(isdigit(ch)){s = s * 10 + ch - '0'; ch = gtc();}s *= w;}inline void write(ll x){if(x < 0){putchar('-'); x = -x;}if(x > 9){write(x/10);}putchar(x % 10 + '0');}ll n, m, q, ans = 0, all = 0;ll nd[MAXN];struct nod{ ll l, r, w;}t[800010];inline void build(ll k,ll l,ll rr){ t[k].l = l, t[k].r = rr; if(t[k].l == t[k].r){ t[k].w = nd[l]; return; } int m = (l + rr) / 2; build(k<<1, l, m); build(k<<1|1, m + 1, rr); t[k].w = max(t[k<<1].w , t[k<<1|1].w);}inline void change_point(ll k, ll x, ll y){ if(t[k].l == t[k].r){ t[k].w = y; return; } ll m = (t[k].l+t[k].r)/2; if(x <= m) change_point(k<<1, x, y); else change_point(k<<1|1, x, y); t[k].w = max(t[k<<1].w, t[k<<1|1].w); }/* 用线段树维护区间最大，找出nd中最大的数xm，num一定≥xm 先使num = xm若num*m > all 直接输出all若num*m < all 考虑维护前缀和，用lower_boudn查找出第一个≥num*n的数那么num = num + (all - num * n) / m ;若 num * m < all ++num;*/ /* 考虑修改，如果不动最大值，或者不超过最大值， 修改all，如果all < num * m 输出num如果> num += (all - num * m); 如果超过最大值将num修改成最大值，判断all与num的关系 如果修改最大值，改大了 同上如果改小了，找出最大值，重复第一次操作*/int main(){//freopen("big.in", "r", stdin);read(n), read(m), read(q);for(int i = 1; i <= n; ++i){read(nd[i]);all+= nd[i];}build(1, 1, n);ans = t[1].w; write(ans > ((all+m-1)/m) ? ans : ((all+m-1)/m)); puts("");ll x, y;for(int i = 1; i <= q; ++i){read(x), read(y);all += (y-nd[x]);nd[x] = y;change_point(1, x, y);ans = t[1].w;write(ans > ((all+m-1)/m) ? ans : ((all+m-1)/m)); puts("");}return 0; }

考场思路

#include<bits/stdc++.h> #define N 1001#define MAXN 400010#define gtc() getchar()#define ll long long#define rg register using namespace std; template <class T>inline void read(T &s){ T w = 1, ch = gtc(); s = 0; while(!isdigit(ch)){if(ch == '-') w = -1; ch = gtc();} while(isdigit(ch)){s = s * 10 + ch - '0'; ch = gtc();} s *= w;} inline void write(ll x){ if(x < 0){ putchar('-'); x = -x; } if(x > 9){ write(x/10); } putchar(x % 10 + '0');} ll n, m, q; ll nd[MAXN]; ll sum = 0;ll xm = -1;ll num = 0;ll ans = 0;struct nod{ ll l, r, w;}t[8000001]; inline void build(ll k,ll l,ll rr){ t[k].l = l, t[k].r = rr; if(t[k].l == t[k].r){ t[k].w = nd[l]; return; } int m = (l + rr) / 2; build(k<<1, l, m); build(k<<1|1, m + 1, rr); t[k].w = max(t[k<<1].w , t[k<<1|1].w);}inline void change_point(ll k, ll x, ll y){ if(t[k].l == t[k].r){ t[k].w = y; return; } ll m = (t[k].l+t[k].r)/2; if(x <= m) change_point(k<<1, x, y); else change_point(k<<1|1, x, y); t[k].w = max(t[k<<1].w, t[k<<1|1].w);} int id = 0;ll all = 0;int main(){// freopen("big.in", "r", stdin); read(n), read(m), read(q); for(int i = 1; i <= n; ++i){ read(nd[i]); all += nd[i]; } build(1, 1, n); ans = t[1].w; num = ans; if(num * m >= all){ cout << num << endl; } else { num += ((all - num * m) / m); if(all > num * m) ++ num; cout << num << endl; } int x, y; for(int i = 1; i <= q; ++i){ read(x), read(y); all += (y-nd[x]); nd[x] = y; change_point(1, x, y); ans = t[1].w; num = ans; if(all > num * m){ num += ((all - num * m) / m); if(num * m < all) ++ num; write(num); puts(""); continue; } else { write(num); puts(""); continue; } }