题解：P17831 [CSP-S 2026] 能量水晶

lailai0916 · 2026-10-31 18:21:53 · 题解

解题思路

将 a 升序排序，最优选择可取为连续区间 [l,r]，代价为：

维护前缀最优长度 k。加入 a_r 后，只可能改进为 k+1，因此只检查末尾 k+1 项。可行则增长，否则左端右移 1，维持长度；窗口本身允许暂不合法。最终长度即答案。

总时间复杂度 O(n\log n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=500005;
ll a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int l=1;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i];
        if(a[i]*(i-l+1)-sum>m)sum-=a[l++];
    }
    cout<<n-l+1<<'\n';
    return 0;
}