3104.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3104  User Id:fzk 
Memory:448K  Time:981MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
//#include <algorithm>
//using namespace std;

int a[100000], k, n;
long long s;
bool check( int t ) {
	long long sum = 0;
	if( ( s - (long long)t*n )/(k-1) > t )
		return false;
	
	for( int i=n-1; i>=0; i-- )
		if( a[i] > t ) {
			sum += (a[i]-t+k-2)/(k-1);
			if( sum > t )
				return false;
		}
	return sum <= t;
}

int main( ) {
	int max = 1, min = 0;
	scanf( "%d", &n );
	int i;
	s = 0;
	
	for( i=0; i<n; i++ ) {
		scanf( "%d", &a[i] );
		s += a[i];
		if( a[i] > max )
			max = a[i];
	}
	
	scanf( "%d", &k );
	
	for( i=0; i<n; i++ )
		if( (a[i]+k-1)/k > min )
			min = (a[i]+k-1)/k;
	
	min--;
	
	if( k == 1 ){
		printf( "%d\n", max );
		return 0;
	}

	int c;

	while( max > min ) {
		c = (max+min)/2;
		if( check( c ) )
			max = c;
		else
			min = c+1;
	}
	printf( "%d\n", max );
	return 0;
}