Boboniu Chats with Du
题意
n 个快乐因子有两种， 一种大于m ，一种小于等于m ，某一天选了第一种时 ，接下来的 d天(不包括选的这一天) 都会被禁言，不能累加别的快乐因子。若选择了第二种则没有影响 ，问怎样选择才能使 n天的快乐因子和最大
思路
枚举选多少个第一种快乐因子即可 首先若选第一种快乐因子肯定选大的，因为选了后同样都是禁言 d天第二种快乐因子也类似 能选就选大的，所以先将两种按降序排序，然后枚举选多少次第一种快乐因子，将res 赋初值为sum1[n] 所以可以不用枚举等于 0的情况
还需要注意的是，若将大于 m 的快乐因子放在最后一天，只会被禁言一天，所以每次枚举都将其中一个放在最后一天
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; const int N = 100100; LL n, d, m; LL a[N], b[N]; LL sum1[N], sum2[N]; bool cmp(int a, int b) { return a > b; } void solve() { cin >> n >> d >> m; LL cnt1 = 0, cnt2 = 0; for (LL i = 1; i <= n; ++i) { LL x; cin >> x; if (x <= m)a[++cnt1] = x; else b[++cnt2] = x; } sort(a + 1, a + cnt1 + 1, cmp); sort(b + 1, b + cnt2 + 1, cmp); for (LL i = 1; i <= n; ++i) sum1[i] = sum1[i - 1] + a[i]; for (LL i = 1; i <= cnt2; ++i) { sum2[i] = sum2[i - 1] + b[i]; } LL res = sum1[n]; for (LL i = 1; i <= cnt2; ++i) { //枚举选几个 大于 m 的 LL sum = sum2[i]; LL rem = (i - 1) * (d + 1) + 1; if (rem > n)break; rem = n - rem; res = max(res, sum + sum1[rem]); } cout << res << endl; } int main(){ //int t; cin >> t; //while(t--) solve(); return 0; }
