Решение задачи Средний класс с Codeforces

Без пояснения   Просмотров: 162

Давным-давно Берляндия была маленькой страной, в которой проживало только n человек. Каждый из них имел некоторое количество сбережений: у i-го человека было ai бурлей.

Правительство считало человека богатым, если у него было хотя бы x бурлей. Чтобы увеличить количество богатых людей в Берляндии, решили провести несколько реформ. Каждая реформа выглядела следующим образом:

правительство выбирает некоторое подмножество людей (возможно, всех);
правительство забирает все сбережения у выбранных людей и перераспределяет их среди выбранных людей поровну.
Например, представим сбережения как список [5,1,2,1]: если правительство выбирает 1-го и 3-го человека, то оно, сначала заберет у них все 5+2=7 бурлей, а потом вернет каждому по 3.5 бурлей. В результате сбережения примут вид [3.5,1,3.5,1].

Много информации было потеряно с того времени, поэтому мы не знаем, сколько реформ было проведено и на ком. Все, что мы можем — это попросить вас посчитать максимально возможное количество богатых людей после некоторого (возможно нулевого) количества реформ.

Код 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ll t,n,x;
	ll a[100005];
	cin >>t;
	while(t--){
		cin >>n >>x;
		ll sum=0;
		for(int i =0;i<n;i++){
			cin >>a[i];
		}
		sort(a,a+n);
		int k=0;
		for(int i=n-1;i>=0;i--){
			sum+=a[i]-x;
			if(sum<0){
				break;
			}
			k++;
		}
		cout <<k;
		cout <<endl;
	}
 
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта