题意:
有n个磁盘,大小为a[],要更新成b[],问最小需要多少个多少额外的开销能完成更新,并且没有数据损失。
思路:
先做a[i] <= b[i]的,再做a[i] > b[i]的。
a[i] <= b[i]的按照a[i]从小到大排序,
a[i] > b[i]的按照b[i]从大到小排序。。。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int, int>
#define MP make_pair
#define inf 0x3f3f3f3f
#define mod 1000000007
#define eps 1e-12
#define Pi acos(-1.0)
#define N 2000050
int n;
int a[N], b[N], idd[N], id[N];
bool cmp(int x, int y){
return b[x] > b[y];
}
bool cmp2(int x, int y){
return a[x] < a[y];
}
bool check(LL v){
for(int i = 1; i <= n; ++i){
int u = idd[i];
if(a[u] <= b[u]){
if(v < a[u]) return 0;
v += b[u] - a[u];
}
}
for(int i = 1; i <= n; ++i){
int u = id[i];
if(a[u] > b[u]){
if(v < a[u]) return 0;
v += b[u] - a[u];
}
}
return v >= 0;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%d%d", &a[i], &b[i]);
id[i] = idd[i] = i;
}
sort(id + 1, id + 1 + n, cmp);
sort(idd + 1, idd + 1 + n, cmp2);
LL L = 0, R = 1LL << 60;
while(L < R){
LL mid = (L + R) / 2;
if(check(mid))
R = mid;
else L = mid + 1;
}
cout << L << endl;
return 0;
}