题解：AT_arc197_b 大于均值

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)$ 。

CPP

#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;
}

题解：AT_arc197_b 大于均值

文章操作

AT_arc197_b 大于均值

解题思路

相关推荐

评论

题解：AT_arc197_b 大于均值