推导贪心条件

排序

二分

输出

 

//#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;const int MAXN = 1e6 + 10;pair <ll, ll> arr[MAXN];int N;bool cmp(pair <ll, ll> a, pair <ll, ll> b)
{return a.second < b.second;
}bool judge(int x)
{ll sum = x;for(int i = 0; i < N; i++){sum += arr[i].first;if(sum > arr[i].second)return false;}return true;}void bsearch()
{int fst = 0, lst = MAXN, mid, ans;if(!judge(0)){cout<<"-1"<<endl;return ;}while(fst <= lst){mid = (fst + lst) / 2;if(judge(mid)){ans = mid;fst = mid + 1;}elselst = mid - 1;}cout<<ans<<endl;}int main()
{//ios::sync_with_stdio(false);//cin.tie(0);     cout.tie(0);cin>>N;for(int i = 0; i < N; i++)cin>>arr[i].first>>arr[i].second;sort(arr, arr + N, cmp);bsearch();return 0;
}