洛谷p2123皇后游戏

https://www.luogu.com.cn/problem/P2123

题目背景
还记得 NOIP 2012 提高组 Day1 的国王游戏吗？时光飞逝，光阴荏苒，两年过去了。国王游戏早已过时，如今已被皇后游戏取代，请你来解决类似于国王游戏的另一个问题。

题目描述
皇后有 n 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 n 位大臣颁发奖金，其中第 i 位大臣所获得的奖金数目为第i－1 位大臣所获得奖金数目与前 i 位大臣左手上的数的和的较大值再加上第 i 位大臣右手上的数。

形式化地讲：我们设第 i 位大臣左手上的正整数为 ai，右手上的正整数为 bi，则第 i 位大臣获得的奖金数目为 ci可以表达为：

当然，吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。

注意：重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

看的这个…弱鸡完全做不出来… 浅谈邻项交换排序的应用以及需要注意的问题

const int MAX=20000+10;
int t,n;
ll ans,sum;
pair<int,int> p[MAX];
int cmp(pair<int,int>  x,pair<int,int> y){
	if(min(x.first,y.second) == min(x.second,y.first)) return x.first < y.first;
	return min(x.first,y.second) < min(x.second,y.first);
}
int main(){
	freopen("in","r",stdin);
	sf(t);
	while(t--){
		sf(n);
		fi(i,0,n){
			sf(p[i].first);sf(p[i].second);
		}
		sort(p,p+n,cmp);
		ans = sum =0;
		fi(i,0,n){
			sum += p[i].first;
			ans = max(ans,sum) + p[i].second;
		}
		printf("%lld\n",ans);
	}
	return 0;
}