[TIOJ] 1406. 魚 FISH

題目連結:http://tioj.infor.org/problems/1406

---

右界設太大浪費了3hr debug...
回到正題，應該不難猜出可以對答案二分搜，而驗證答案的時候也很簡單，想法就是如果我有多我就往右運過去，然後如果有人少他就拿走那些，如果還不夠就跟右邊的再要，所以其實就是開個變數存說多多少/少多少，如果是多的話運走的時候要是變成小於零，就讓它變成零，但是如果是少的話就算變成小於零，還是要維持著。最後只要看剩下來的是否大於等於零即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<lld,lld> PLL;
#define FF first
#define SS second

const int N = 100000 + 5;

int n;
PLL arr[N];

inline bool isOK(lld);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	while(cin>>n){
		lld l=0, r=0;
		for(int i=0;i<n;i++){
			cin>>arr[i].FF>>arr[i].SS;
			r=max(r, arr[i].SS);
		}
		r++;
		while(r-l>1){
			lld mid = (l+r)>>1;
			if(isOK(mid)) l=mid;
			else r=mid;
		}
		cout<<l<<'\n';
	}
	return 0;
}

inline bool isOK(lld x){
	lld con = arr[0].SS-x;
	for(int i=1;i<n;i++){
		if(con >= 0) con = max(0LL, con+arr[i-1].FF-arr[i].FF);
		else con+=arr[i-1].FF-arr[i].FF;
		con += arr[i].SS-x;
	}
	return con>=0;
}