codeforces Round 794 题解

D. Traps（贪心）

题意：有 $n$ 个陷阱，每个陷阱有一个伤害值 $a_i$ ，现在你会一个一个走过所有陷阱。你有 $k$ 次操作，每次可以选择跳过某个陷阱，不受这个陷阱的伤害，但是后面所有陷阱的伤害会上升一个单位，问你走过所有的陷阱的最小伤害是多少？

假设我们跳过的陷阱下标分别为 $p_1, p_2, p_3, \dots, p_k, (p1 < p2 < p3 < \dots <p_k)$ ，让我们计算一下跳过每个陷阱对伤害造成的贡献。

当跳过$p1$这个陷阱的时候，我们会减少 $a{p1}$ 点伤害，后面所有陷阱的伤害会增加$1$，即增加 $n - p_i$ 点伤害，注意我们后面还有 $k-1$ 次跳过机会，又会减少 $k-1$ 点伤害，因此跳过这个陷阱会减少 $a{p_1} - (n - p_1) + (k - 1)$ 点伤害。

跳过$p2$这个陷阱同理，会减少 $a{p2}$ 点伤害，后面所有陷阱增加 $1$ 点，即增加 $n-p_2$ 点伤害，后面有 $k-2$ 次跳过机会，会减少 $k-2$ 点伤害，计算一下就是减少$a{p_2} - (n - p_2) + (k - 2)$ 点伤害。

后面依次同理。

那么我们最后的伤害就是

$$\begin{array} {lr} \sum_{i = 1} ^ n a_i - \sum_{j = 1} ^ k(a _ {p _ j} - (n - p_j) + (k - j))\\ = \sum_{i = 1} ^ na_i - (\sum_{j = 1} ^ k a_{p_j} - n * k + \sum _{j = 1} ^ k p_j + k ^ 2 - \sum_{j = 1} ^ k j)\\ = \sum_{i = 1} ^ n a_i - (\sum_{j = 1} ^k a_{p_j} + \sum_{j = 1} ^ kp_j) + n * k - k ^ 2 + \frac{k * (k + 1)}{2}\\ = \sum_{i = 1} ^ n a_i + n * k - \frac{k * (k - 1)}{2} - \sum_{j = 1}^k{(a_{p_j} + p_j)} \end{array}$$

注意前面一大坨都是定值，因此只需要后面的尽量大就行。

那么我们可以另 $b_i = a_i + i$ ，然后选取前 $k$ 个最大的 $b_i$ 就行，然后就可以得到答案。

void solve(void){
    ll n, k;
    scanf("%lld %lld", &n, &k);
    vector<ll> v1(n+1), v2(n+1);
    for(int i = 1;i <= n;i++){
        scanf("%lld", &v1[i]);
        v2[i] = v1[i] + i;
    }
    ll ans = accumulate(v1.begin()+1, v1.end(), 0ll);
    ans += n * k - k * (k - 1) / 2;
    sort(v2.begin() + 1, v2.end());
    for(int i = 1;i <= k;i++){
        ans -= v2[n-i+1];
    }
    printf("%lld\n", ans);
}

---

E. MEX vs DIFF（贪心+二分）

题意：给定一个 $n$ 个数字的数组 $a$ ，有 $k$ 次操作，每次操作可以选择任意一个数字变成任意一个非负数，问 $DIFF(a) - MEX(a)$ 的最小值，其中 $DIFF(a)$ 是 $a$ 数组中不同数字个数。

第一反应贪心：考虑尽量减小 $DIFF$ 与增大 $MEX$ ，那么我们优先找尽量大的值去填 $MEX$ ，如果大的不够那么就拿前面重复的数字去填 $MEX$ ，直到没有可填的数字或者操作次数不够。注意如果操作次数不够，那么 $MEX$ 的上限已经定下来了，这个时候我们就要尽量减小$DIFF$ ，即优先拿大的数字里面出现次数较小的数字去填，这样才能使 $DIFF$ 较小。

证明：

设我们当前选择的数字为$a_i$，且当前数字仅出现一次，即 $count(a_i) = 1$ ，那么我们改变当前数字会使 $DIFF-1$ ， $MEX+1$，这样对答案的贡献就是 $DIFF - 1 - (MEX + 1) = DIFF - MEX - 2$ 。

如果当前数字不仅出现一次，即 $count(a_i) > 1$ ，那么我们此次操作会使 $MEX + 1$ ，对答案的贡献是 $DIFF - (MEX + 1) = DIFF - MEX - 1$。

而且在我们填 $MEX$ 的过程中不仅仅会使 $MEX$ 仅增加 $1$ ，此时对答案的贡献会更大，这样操作下去一定是最优解。

剩下的就是怎么操作这个贪心了。

我使用的是二分贪心，我们二分 $MEX$ ，如果当前通过 $k$ 次操作能实现 $mid$ ，那么我们使 $MEX = mid + 1$ ，否则 $MEX = mid$ ，这样下去 $MEX - 1$即是我们的目标 $MEX$ 。

然后在尽量去减小 $DIFF$ 就可以了，获取比 $MEX$ 大的所有数字的次数，出现次数小的先删，直到 $k$ 次删满或者后面没得删了为止。

注意当 $MEX == DIFF$时为 $0$ ，因此答案就是比 $MEX$ 大的数字中无法删除的数字的个数。

int num[maxn];
vector<int> v;
int n, k;
int check(int mid){
    int pos = lower_bound(v.begin(), v.end(), mid) - v.begin(); // 有多少个数字比mex小
    if(mid - pos <= k && n - pos >= mid - pos) return 1; // 如果中间的空格小于k，多的数字能够把空填满
    return 0;
}
inline void solve(void){
    v.clear();
    scanf("%d %d", &n , &k);
    
    for(int i = 1;i <= n;i++){
        scanf("%d", &num[i]);
        v.push_back(num[i]);
    }
    sort(num + 1, num + 1 + n);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int l = 0, r = 4e5;
    while(l < r){
        int mid = (l + r) / 2;
        if(check(mid)){
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    int mex = l-1;
    int st = n+1;
    for(int i = 1;i <= n;i++){
        if(num[i] > mex){
            st = i;
            break;
        }
    }
    if(st == n+1){
        puts("0");
        return;
    }
    int tot = 1;
    vector<int> tmp;
    for(int i = st+1;i <= n;i++){
        if(num[i] == num[i-1]){
            tot ++;
        }else{
            tmp.push_back(tot);
            tot = 1;
        }
    }
    tmp.push_back(tot);
    sort(tmp.begin(), tmp.end());
    int ans = tmp.size();
    for(int i = 0;i < tmp.size();i++){
        if(tmp[i] <= k){
            k -= tmp[i];
            ans--;
        }else break;
    }
    printf("%d\n",ans);
}

---