Educational Codeforces Round 85 B. Middle Class（排序/贪心/水题）

2021-02-20 21:21

阅读：536

标签：break color next std clipboard bsp mat lan pac

Many years ago Berland was a small country where only $n$

The government considered a person as wealthy if he had at least $x$

the government chooses some subset of people (maybe all of them);
the government takes all savings from the chosen people and redistributes the savings among the chosen people equally.

For example, consider the savings as list $[5, 1, 2, 1]$

A lot of data was lost from that time, so we don‘t know how many reforms were implemented and to whom. All we can do is ask you to calculate the maximum possible number of wealthy people after several (maybe zero) reforms.

Input

The first line contains single integer $T$

Next $2 T$

The second line contains $n$

It‘s guaranteed that the total sum of $n$

Output

Print $T$

Example

Input

Copy

Output

Copy

2
4
0
3
可以贪心地考虑，只需要超过x或者大于等于x就是富有的，那么何必多浪费钱呢？如果一个人的钱数超过x，就先++ans，再把超过的钱累加到变量sum里，最后按照钱数从小到大排序，从后往前扫一遍数组，对于不足x的人看看能否用sum使之钱数达到x。（为保证人数尽可能多，先满足钱数与x差距小的人）
注意：It‘s guaranteed that the total sum of  $n$  所以这个复杂度是没问题的。

#include using namespace std;
int n,x,a[100005];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&x);
        int i;
        int ans=0; 
        long long sum=0;//sum存储的是超过x的钱数 
        for(i=1;i)
        {
            scanf("%d",&a[i]);
            if(a[i]>=x)ans++,sum+=a[i]-x;
        }
        sort(a+1,a+n+1);
        for(i=n;i>=1;i--)
        {
            if(sum0)break;
            if(a[i]x)
            {
                if(x-a[i]sum)
                {
                    ans++;
                    sum-=(x-a[i]);
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
 }

Educational Codeforces Round 85 B. Middle Class（排序/贪心/水题）

标签：break color next std clipboard bsp mat lan pac

原文地址：https://www.cnblogs.com/lipoicyclic/p/12678567.html

上一篇：Visual Studio Code 1.44 设置简体中文界面语言（小白图文教程）

下一篇：【python】python中的字符串

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Educational Codeforces Round 85 B. Middle Class（排序/贪心/水题）
文章链接：http://soscw.com/index.php/essay/58155.html

亲，登录后才可以留言！

Educational Codeforces Round 85 B. Middle Class（排序/贪心/水题）

评论

热门文章

推荐文章

最新文章

置顶文章