TIOJ 1406 魚 FISH [Greedy]

    poao899    1556K    545MS    G++     0.68K     2010-03-28 12:31:29                                     .


奇怪為什麼之前想這麼久

明明沒有很難ˇ    頗可愛的題目>//<

















//*****************************

#include<stdio.h>
long long p[100010], f[100010], mid, l, r;
int n;
long long getl(){
	long long g=0;int c=getchar();
	while(c==10||c==32||c==9)c=getchar();
	while(c>='0'&&c<='9'){
		g=g*10+c-48;
		c=getchar();
	}
	return g;
}
bool test(){
	long long rest=0;
	f[0]=mid;
	for(int i=1; i<=n; i++){
		if(rest)rest-= p[i]-p[i-1];
		rest+= f[i]-mid;
	}
	return rest>=0;
}
int main(){
	while(~scanf("%d", &n)){
		l=9223372036854775807LL; r=-9223372036854775807LL;
		for(int i=1; i<=n; i++){
			p[i]=getl(); f[i]=getl();
			if(f[i]>r)r=f[i];
			if(f[i]<l)l=f[i];
		}
		while(l!=r){
			mid=(l+r+1)/2;
			if(test())l=mid;
			else r=mid-1;
		}
		printf("%I64d\n",l);
	}
}