3138624_ac_563ms_608k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 57 行

#include <stdio.h>

int a[100001];
int n, k;

int main()
{
	int i, t, fail;
	int min, mid, max;

	scanf("%d",&n);
	max = 0;
	for(i = 0; i < n; i++)
	{
		scanf("%d",&a[i]);
		if(a[i] > max)
		{
			max = a[i];
		}
	}
	scanf("%d",&k);
	k--;
	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("%d\n",min);
	return 0;
}