【CSP-S 2026】能量水晶神秘做法
2026-11-07 19:55:22
发布于:广东
15阅读
0回复
0点赞
非常神秘的做法
因为考试的时候少写了两个q.size()导致只拿了55
因为当数组是单调递增的时候,用队列就是单调的,于是只需要用滑动窗口,当所用增加的值大于m时,只需要把队头消耗最大的出队即可。
初始化第一个点,从第二个点开始遍历到n,假设当前点的值为要加到的值,将当前下标入队并判断队列是否合法,最后用ans存储ans和q.size()的最大值即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 9;
ll n, m, a[N], dp[N];int ans = 1;
queue <ll> q;
int main(){
//freopen("crystal.in", "r", stdin);
//freopen("crystal.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
sort (a + 1, a + n + 1);
dp[1] = 0;
q.push(1);
for (int i = 2; i <= n; i++){
dp[i] = dp[i - 1] + (a[i] - a[i - 1]) * q.size();
q.push(i);
while (dp[i] > m && q.size()){
int f = q.front();
q.pop();
dp[i] -= a[i] - a[f];
}
ans = max(ans, int(q.size()));
}
cout << ans;
return 0;
}
这里空空如也


有帮助,赞一个