CF1394A Boboniu Chats with Du 题解

题面描述

CF1394A Boboniu Chats with Du

solve

今天初赛模拟做到了这道题，回过头来看挺简单的，但是还是填错了一个

首先分成 $ >m $和 $ m≤m $ 的两组 (big) 和 (small)，分别从大到小排序。

枚举取几个(big)中的数，然后(small)里面也是从大到小取

注意一个细节，就是大的放在最后一个可以节约一点被禁言的时间，所以占掉的时间就是 ((i-1) imes (m+1)+1)

我感觉主人公就是CY，一天不被禁言就难受

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define int long long

const int MAXN = 1e5 + 5;

int big[MAXN], small[MAXN], sum[MAXN];
int p1 = 1, p2 = 1;
int n, m, k, x;

signed main() {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
        cin >> x;
        if(x <= k) {
            small[p1++] = x;
        } else {
            big[p2++] = x;
        }
    }
    sort(small + 1, small + 1 + p1, greater<int>());
    sort(big + 1, big + 1 + p2, greater<int>());
    for(int i = 1; i <= p1; i++) {
        sum[i] = sum[i - 1] + small[i];
    }
    int ans = sum[p1], cur = 0;
    for(int i = 1; i <= p2; i++) {
        cur += big[i];
        int days = (i - 1) * (m + 1) + 1; 
        if(days > n) {
            break;
        }
        int left = min(n - days, p1); 
        ans = max(ans, sum[left] + cur);
    }
    cout << ans << endl;
}