『贪心』服务器需求

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

我们设答案为$x$，那么首先答案需要满足$x\ge \forall a_i$.

然后我们来考虑如何分配这$x$台机器，我们发现：

由于机器的使用天数是不连续的，每一台机器在每一天的贡献是独立的，因此只需要满足$\sum a_i\le x\times m$.

然后就得到结论： $$\max (\underset{i=1}{\overset{n}{\max }}(a_i),\lceil \frac{{\sum }_{i=1}^n{a}_i}{m}\rceil )$$

我们维护最大值（用支持删除修改的set维护/线段树），区间和即可。

说一个使用$set$的小坑点：

$s$中删除所有元素大小为$x$的数，用法是$s.\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{s}\mathrm{e}(x)$.$s$中删除一个元素大小为$x$的数，用法是$s.\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{s}\mathrm{e}(s.\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{d}(x))$.

代码如下：

#include <set> #include <cstdio> #include <iostream> #define int long long using namespace std; const int N = 5e5; int n, m, q, sum(0); int a[N]; multiset<int>s; int read(void) { int s = 0, w = 0; char c = getchar(); while (c < '0' || c > '9') w |= c == '-', c = getchar(); while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar(); return w ? -s : s; } int ans(void) { multiset<int>::iterator it = s.end(); int ans = sum % m ? sum / m + 1 : sum / m; return max(*(--it),ans); } void change(void) { int x = read(), v = read(); s.erase(s.find(a[x])); s.insert(v); sum += -a[x] + (a[x] = v); printf("%lld\n", ans()); return; }