题目翻译

有$n$个数,每个数的值为$a_i$,让你选$k$个数,使得这$k$个数的平均值大于$x$,问这个$k$最大是多少。

题目分析

考虑贪心。首先求出所有数的平均值,然后每次去掉最小的那个数,这样平均值肯定会上涨。涨到这个平均值大于$x$的时候就可以输出解了。既然要去掉最小的数,可以使用优先队列来维护(在线),或者直接用$sort$(离线),总时间复杂度$O(n\log_2 n)$。$n\le10^5$,可放心食用。

但是这里还有一个要注意的点,由于是要求平均值,所以至少要先把所有数加起来,由于$a_i\le 10^9,n\le10^5$,所以$sum \le 10^{14}$,$long long$安排上。

如果还是不明白的话,可以参考代码的注释

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int t,n;
const int maxn=100005;
priority_queue <long long, vector<long long>, greater<long long> > q;    //优先队列,因为是要去掉最小的,所以要使用greater
long long sum,x;    //sum是当前和,x前面有说
double pj;            //pj 平均
int main(){
    cin>>t;
    while(t--){
        cin>>n>>x;sum=0;                //先清空,因为有多组数据
        for(int i=1;i<=n;++i){
            int k;                      //读入一个数
            cin>>k;
            sum+=k;                     //sum加上
            q.push(k);                  //入队
        }
        pj=(double)sum/n;               //先算平均值
        while(pj < x && !q.empty()){
            //如果平均值还小于x,就要再删
            //但是有可能删空了,没得删,所以要加个!q.empty()
            long long out=q.top();      //取出首元素
            sum-=out;--n;               //sum减掉,现在是总共选择少了一个,所以--n,这个n是最后的答案
            pj=1.0*sum/n;               //重新计算平均值,因为sum和n都是longlong类型,要加个类型转换
            q.pop();                    //出队
        }
        cout<<n<<endl;                  //输出解
        while(!q.empty())               //因为有多组数据,所以要先清空队列
        q.pop();
    }
    return 0;
}

发表评论

邮箱地址不会被公开。