题目链接
分析
显然 \(c_n\) 为最大值。
考虑使用邻项微扰，原本的第 \(n-1\) 项编号为 \(i\)，第 \(n\) 项编号为 \(j\)。设前 \(n-2\) 项的 \(a_k\) 之和为 \(s\)。
交换前，
交换后，\(c_n'=\max(c_{n-2}+b_i+b_j, s+a_j+b_i+b_j, s+a_i+a_j+b_i)\)。
若交换不会使得答案变得更优，即 \(c_n\le c_n'\)。
这并不是一个合格的 偏序关系，因为没有 传递性，所以不能直接套用该关系作为比较函数进行排序。
进一步地推导，可以将该关系抽象为 \(a_i=\min(a_i, b_i, a_j, b_j)\vee b_j=\min(a_i, b_i, a_j, b_j)\)。
将数据分成下标统一的两组 \((a_i, b_i),(a_j, b_j)\)，只需要比较两组之间的最小值即可。
1. \(a_i\le b_i,a_j\le b_j\)
若 \(a_i\le a_j\)，则 \(a_i=\min(a_i, b_i, a_j, b_j)\)；否则 \(a_j=\min(a_i, b_i, a_j, b_j)\)。
2. \(a_i\le b_i,a_j\ge b_j\)
最小值一定为 \(a_i,b_j\) 之一，令 \(i\) 在 \(j\) 前。
3. \(a_i\ge b_i,a_j\le b_j\)
最小值一定为 \(a_j,b_i\) 之一，令 \(j\) 在 \(i\) 前。
4. \(a_i\ge b_i,a_j\ge b_j\)
若 \(b_i\le b_j\)，则 \(b_j=\min(a_i, b_i, a_j, b_j)\)；否则 \(b_i=\min(a_i, b_i, a_j, b_j)\)。
这样一来，我们把整个序列分成两块，前面一块为 \(a_i\le b_i\)，后面一块为 \(a_i> b_i\)；在块中的关系具有传递性。按照这种比较方式进行排序，可以确保 \(\forall p_i<p_j,\min(b_j, a_i)\le \min(b_i, a_j)\)，\(p_i\) 为 \(i\) 所在位置。
代码
#include <iostream>
#include <algorithm>
#include <ctime>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const ll INF=1LL<<60;
struct node {
int x,y;
bool s;
bool operator<(const node &b)const{
if (s!=b.s)
return s;
return s?x<b.x:y>b.y;
}
}p[maxn];
int read() {
int res=0,p=1;
char ch=getchar();
while(!isdigit(ch)) {
if (ch=='-')
p=-1;
ch=getchar();
}
while(isdigit(ch))
res=res*10+ch-'0',ch=getchar();
return res*p;
}
int main() {
int T=read();
while (T--) {
int n=read();
for (int i=1;i<=n;i++)
p[i].x=read(),p[i].y=read(),p[i].s=p[i].x<=p[i].y;
sort(p+1, p+1+n);
ll ans=p[1].x+p[1].y,sum=p[1].x;
for (int i=2;i<=n;i++) {
sum+=p[i].x;
ans=max(ans, sum)+p[i].y;
}
cout<<ans<<endl;
}
return 0;
}