Boboniu Chats with Du

Created by LXC on Tue Jan 16 14:50:48 2024

https://codeforces.com/problemset/problem/1394/A

ranting: 1800

tag: dp, greedy, sortings, two pointers

problem

你用过 QQ 吗？在 QQ 群里，管理员可以禁言用户。

在 Boboniu 的 QQ 群里，小D 每天都开 Boboniu 的玩笑。

小D 会在群里待 $n$ 天，Boboniu 的心情是 $m$。在第 $i$ 天，如果 小D 没被禁言，他会开一个严重程度为 $a_i$ 的玩笑；如果开的玩笑严重程度大于 $m$，他就会被 Boboniu 禁言 $d$ 天，也就是说，在第 $i+1,i+2,\dots,\min(i+d,n)$ 天，他都会被禁言。

请求出 $a$ 所有置换中严重程度之和的最大值。

solution

对于a数组中元素，将小于等于m的分到x数组，将大于m的分到y数组。并将x和y数组排序。令xsz和ysz分别是x和y数组的大小。

我们可以枚举使用y中数的个数b，对于不同的b，求贡献最大值。

注意到，我们每使用一个y中的数就需要减少d个数。那么b最少是多少？

为了最小化使用y中的数，我们每使用一个就将y中的数减少d个，因此最少能使用$\lceil \frac{ysz}{d+1} \rceil$个。

我们从$\lceil \frac{ysz}{d+1} \rceil$开始枚举b，让b不断增大。

开始求每个b的贡献，使用b个y中数组，可以将其中一个安排到最后使用，那么需要跳过$(b-1)d$个数。已知y中剩余的数还有$ysz-b$个，我们还需要从x中移除$(b-1)d-(ysz-b)$个数。为了让贡献最大化，我们使用的b个y中数是尽量大的，而移除的x中的数是尽量小的。对于x中剩余的数可以用前缀和快速求出。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, d, m;
    cin >> n >> d >> m;
    vector<ll> x, y;
    for (int i = 0; i < n; i++) {
        ll t;
        cin >> t;
        (t > m ? y : x).push_back(t);
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    ll xsz = x.size(), ysz = y.size();
    vector<ll> px(xsz, -1);
    function<ll(int)> pre = [&](int u) -> ll {
        if (u < 0)
            return 0;
        if (px[u] != -1)
            return px[u];
        return px[u] = pre(u - 1) + x[u];
    };
    ll b = (ysz + d) / (d + 1);
    ll s = 0;
    for (int i = 0; i < b; i++) {
        s += y.back();
        y.pop_back();
    }
    ll ans = pre(xsz - 1) + s;
    while (y.size()) {
        s += y.back();
        b++;
        y.pop_back();
        ll r = (b - 1) * d - y.size();
        if (r <= xsz) {
            ans = max(ans, pre(xsz - 1) - pre(r - 1) + s);
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}