站外题求助约为橙题难度

rt 有 N 个人生活在某个不知名的小国，每个人都有一些积蓄，一开始每个人的积蓄分别为

a_1,a_2,\cdots a_n

。

国王想要推行共同富裕的政策。他认为如果一位居民的积蓄至少为 X，那么他就是富裕的。

为了增加富裕人口的数量，国王开始推行一项改革，方式如下：

选择一部分居民（可以是所有居民）:

拿走这些居民的全部积蓄，并将这些积蓄在所选的居民当中平分。

例如：如果所有居民的积蓄分别为 [5,1,2]，国王选择第一位和第三位居民进行改革，那么他们的财富值将会变成 [3.5,1,3.5]。

国王现在想知道，在他进行任意次（可以是 0 次）改革之后，最多能够出现多少位富裕的居民？

多组数据，n的和不超过1e5，其余数字不超过1e9。

我的思路：贪心，题目可以转化成选择y个人，使得其拥有的钱数

\ge y\times X

，求

y

的最大值。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int t,n,k,a[200010]; 
int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		sort(a+1,a+1+n);
		int sum=0,ans=0;
		for(int i=n;i>=1;i--){
			ans++;
			if((sum+a[i])<ans*k){
				ans--;
				break;
			}
			sum+=a[i];
		}
		cout<<ans<<'\n';
	}
	return 0;
}

站外题求助约为橙题难度

讨论操作

回复

相关推荐

站外题求助约为橙题难度