Flowers

The first line contains an integer ${T}$ ( $1 \le T \le 10$ ) --- the number of test cases.
In the first line of each test case, there are two integers ${N}$ , ${M}$ ( $1 \le N, M \le 300\,000$ ) --- the number of flowers' species and the number of flowers in a bunch.
In the second line of each test case, there are ${N}$ integers --- the ${i}$ -th integer indicates $a_i$ ( $1 \le a_i \le 10^9$ ), the number of ${i}$ -th species' flowers.

C++14(g++5.4) 解法, 执行用时: 195ms, 内存消耗: 2596K, 提交时间: 2020-10-11 20:32:47

#include<cstdio>
#include<algorithm>
using namespace std;
long long ans,m,tot,a[300005];
int T,n,i,k;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%lld",&n,&m);
		if (m>n) printf("0\n");
		else
		{
			ans=0;
			for(i=1;i<=n;i++)
			{
				scanf("%lld",&a[i]);
				ans+=a[i];
			}
			sort(a+1,a+n+1);
			reverse(a+1,a+n+1);
			k=1;
			while(ans/m<a[k]&&m>1)
			{
				ans-=a[k++];
				m--;
			}
			printf("%lld\n",ans/m);
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 149ms, 内存消耗: 2680K, 提交时间: 2020-10-07 19:48:52

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int nx=3e5+5;
ll a[nx];
int n,m;
bool ck(ll x){
	ll s=0;
	for(int i=0;i<n;++i)
		s+=a[i]>=x?x:a[i];
	return s>=x*m; 
}
int main(){
	int t;scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;++i)scanf("%lld",a+i);
		ll l=-1,r=3e14+1,mid;
		while(l+1<r){
			mid=l+r>>1;
			if(ck(mid))l=mid;
			else r=mid;
		}printf("%lld\n",l);
	}
}

详情