3138686_wa.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

__int64 a[100001];
int n;

int main()
{
	int i, fail, cas;
	__int64 min, mid, max, m;
	__int64 k, t;

	scanf("%d",&cas);
	while(cas-- > 0)
	{
		scanf("%d",&n);
		max = 0;
		for(i = 0; i < n; i++)
		{
			scanf("%I64d",&a[i]);
			if(a[i] > max)
			{
				max = a[i];
			}
		}
		scanf("%I64d%I64d",&m,&k);
		k--;
		k *= m;
		min = 1;
		while(min < max)
		{
			mid = (min+max)>>1;
			t = 0;
			fail = 0;
			for(i = 0; i < n; i++)
			{
				if(a[i] > mid)
				{
					if(k==0)
					{
						fail = 1;
						break;
					}
					t += (a[i]-mid)/k+((a[i]-mid)%k==0?0:1);
					if(t > mid)
					{
						fail = 1;
						break;
					}
				}
			}
			if(fail)
			{
				min = mid+1;
			}
			else
			{
				max = mid;
			}
		}
		printf("%I64d\n",min);
	}
	return 0;
}