第九届河南理工大学算法程序设计大赛 正式赛K：高度期望

单测试点时限: 1.0 秒

内存限制: 512 MB

这里是 $22$ 世纪，有一款神奇的机器，可以使任意一棵树长到任意高度但不超过 $1000$ cm，但是该机器却只能使用一次。为了提升整片树林的平均树高，使得平均树高大于某个值，请设计提升方案。我们的 Boss 对方案本身不感兴趣，你只需要提供提升后需要的机器数量。

输入

第一行 $2$ 个整数 $n$,$ m$, 表示有 $n$ 颗树和期望的最小平均树高 $m$ cm。
之后的一行 $n$ 个整数 $a_1 a_2⋯a_n$，表示 $n$ 颗树的高度。
$0<n≤10^5, 0<m≤10^3, 0<a_1 a_2⋯a_n≤10^3$ 。

输出

输出提升平均树高所需要的最少机器数量。

样例

input

5 1000
1000 1000 1000 500 1000

output

1

Solve

贪心，在平均高度不够的时候，将高度最低的变成$1000$

Code

#include<bits/stdc++.h>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
const int maxn=1e6+10;
const int maxm=1e3+10;
const int inf=(1<<30);
const ll INF=(1LL*1<<60);
using namespace std;
int a[maxn];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int n,m;
	cin>>n>>m;
	int sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	sort(a,a+n);
	int x=n*m;
	int ans=0;
	for(int i=0;i<n;i++)
	{
		if(sum>=x)
			break;
		if(a[i]<m)
		{
			sum+=(1000-a[i]);
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}