题解：AT_arc197_b 大于均值

SunburstFan · 2025-05-10 15:21:05 · 题解

AT_arc197_b 大于均值

解题思路

• 首先对序列 A 排序，并计算其前缀和。
  目标是选出一个子序列，其得分为大于子序列均值的元素数量最大。
  定义得分为 \sum_{i=1}^{|x|} \mathbf{1}\Bigl(x_i > \frac{\sum_{j=1}^{|x|} x_j}{|x|}\Bigr)。

• 对于每个可能的子序列长度 i，累加排序后前 i 个元素的和 S = \sum_{j=1}^i A_j。
  设固定的 D 数量对应于被子序列舍弃的前缀个数 k，使得剩余部分全部大于平均值。
  判断条件为 A_k \cdot i > S, 并使用双指针寻找最小满足条件的 k。

• 最终得分即为最大值 \max_{1\le i\le N}(i - k)，
  其中 i-k 表示选取长度为 i 的子序列中大于均值的元素个数。
  时间复杂度为 O(N\log N)。

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

void FileIO(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair

namespace sunburstfan{
    #define int long long
    const int mod=1e9+7;
    const int N=1e5+5;
    const int INF=1e18+5;

    void solve(){
        int n;
        cin>>n;

        vector<int> a(n+1,INF);
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        sort(a.begin(),a.end());

        int sum=0,k=0,ans=0;
        for(int i=1;i<=n;i++){
            sum+=a[i-1];
            while(k<i&&a[k]*i<=sum)k++;
            ans=max(ans,i-k);
       }   

        cout<<ans<<"\n";
    }
}
using namespace sunburstfan;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T=1; cin>>T;
    while(T--){
        solve();
    }
    return 0;
}