题目大意

给你 $n$ 个硬盘，第 $i$ 个硬盘原来有 $a_i$ 的内存，但是在转化格式之后内存就变成了 $b_i$。在转化格式的时候，全部的资料都需要转移到其他空间，如果空间不够用就可以额外申请空间。在最开始的时候每个硬盘都装满了，求额外申请的空间的最小值。

思路

首先所有的硬盘一共与三种分类：$a_i<b_i$，$a_i=b_i$，$a_i>b_i$。

因为第 $2$ 类对于答案没有影响，所以为了便于处理，我们将第 $2$ 类归入第一类，即 $a_i\le b_i$，$a_i>b_i$。

应该优先处理第 $1$ 类，因为在修改之后剩余的空间是在增加的。

对于第 $1$ 类，应该按 $a_i$ 从小到大处理更优，证明如下：

假设有 $2$ 块硬盘分别是 $(a_1,b_1)$ 和 $(a_2,b_2)$。

如果 $b_1\ge a_2 $：先处理 $a_1$ 再处理 $a_2$，需要的代价是 $a_1$；先处理 $a_2$ 再处理 $a_1$，需要的代价是 $a_2$。因为 $a_1\le a_2$，所以先处理第 $1$ 块更优。

如果 $b_1< a_2$：先处理 $a_1$ 再处理 $a_2$，需要的代价是 $a_1+a_2-b_1$；先处理 $a_2$ 再处理 $a_1$，需要的代价是 $a_2$。因为$a_1+a_2-b_1\le a_2$，所以先处理第 $1$ 块更优。

对于第 $2$ 类，应该按 $b_i$ 从大到小处理更优，证明如下：

假设有 $2$ 块硬盘分别是 $(a_1,b_1)$ 和 $(a_2,b_2)$。

如果 $b_1\ge a_2 $：先处理 $a_1$ 再处理 $a_2$，需要的代价是 $a_1$；先处理 $a_2$ 再处理 $a_1$，需要的代价是 $a_2+a_1-b_2$。因为 $a_1\le a_2+a_1-b_2$，所以先处理第 $1$ 块更优。

如果 $b_1< a_2$：先处理 $a_1$ 再处理 $a_2$，需要的代价是 $a_1+a_2-b_1$；先处理 $a_2$ 再处理 $a_1$，需要的代价是 $a_2+a_1-b_2$。因为$a_1+a_2-b_1\le a_2+a_1-b_2$，所以先处理第 $1$ 块更优。

所以，排序之后模拟整个过程，时间复杂度 $O(n\log n)$。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,c1,c2,ans,cnt;
struct node{int a,b;}s1[N],s2[N];
bool cmp1(node x,node y){return x.a<y.a;}
bool cmp2(node x,node y){return x.b>y.b;}
signed main(){
	cin>>n;
	for(int i=1,a,b;i<=n;i++){
		cin>>a>>b;
		if(a<b) s1[++c1]={a,b};
		else s2[++c2]={a,b};
	}sort(s1+1,s1+1+c1,cmp1),sort(s2+1,s2+1+c2,cmp2);
	for(int i=1;i<=c1;i++){
		if(cnt<s1[i].a) ans+=(s1[i].a-cnt),cnt=0;
		else cnt-=s1[i].a;
		cnt+=s1[i].b;
	}for(int i=1;i<=c2;i++){
		if(cnt<s2[i].a) ans+=(s2[i].a-cnt),cnt=0;
		else cnt-=s2[i].a;
		cnt+=s2[i].b;
	}cout<<ans<<endl;
	return 0;
}