10分 有大佬教一下怎么降时间复杂度吗
查看原帖
10分 有大佬教一下怎么降时间复杂度吗
834070
szz123456楼主2023/4/5 16:23
#include<iostream>
#include<algorithm>
using namespace std;
long long cmp(long long a, long long b)
{
	return a > b;
}
int main()
{
	long long n, sum, q[100], i, j,mid,l,r,s=0;
	scanf_s("%lld%lld", &n, &sum);
	for (i = 0; i < n; i++)scanf_s("%lld",&q[i]);
	sort(q, q + n,cmp);
	l = 0; r = q[0];
	while (l <r)
	{
		mid = (l + r) / 2;
		for ( i = 0; i < n; i++)
		{
			if (q[i] > mid)s += (q[i] - mid);
		}
		if (s > sum)l++;
		else if (s == sum)
		{
			printf("%lld", mid);
			return 0;
		}
		else
			r++;
		s = 0;
	}
	printf("%lld", l);
	return 0;
}
2023/4/5 16:23
加载中...