『贪心』服务器需求

$\mathrm{Problem}$Problem

$\mathrm{Solution}$Solution

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

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

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

然后就得到结论：
$\max(\max_{i=1}^{n}(a_i),\lceil \frac{\sum_{i=1}^{n}a_i}{m}\rceil)$max(i=1maxn​(ai​),⌈m∑i=1n​ai​​⌉)

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

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

• $s$s中删除所有元素大小为$x$x的数，用法是$s.\mathrm{erase}(x)$s.erase(x).
• $s$s中删除一个元素大小为$x$x的数，用法是$s.\mathrm{erase}(s.\mathrm{find}(x))$s.erase(s.find(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;
}