题解:
https://www.luogu.org/problemnew/solution/P2123
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
// Scanner sc=new Scanner(System.in);
int t=(int)in.nval;
// in.nextToken();
while(t-->0) {
in.nextToken();
int n=(int)in.nval;
// in.nextToken();
long sum=0;
Ad[] admin=new Ad[n];
for(int i=0;i<n;i++) {
in.nextToken();
admin[i]=new Ad();
admin[i].l=(int)in.nval;
in.nextToken();
admin[i].r=(int)in.nval;
if(admin[i].l>admin[i].r)
admin[i].d=1;
else if(admin[i].l<admin[i].r)
admin[i].d=-1;
else
admin[i].d=0;
}
Comparator<Ad> cmp=new Comparator<Ad>() {
@Override
public int compare(Ad o1, Ad o2) {
// TODO Auto-generated method stub
if(o1.d!=o2.d)
return o2.d-o1.d;
if(o1.d<=0) return o2.l-o1.l;
return o1.r-o2.r;
}
};
Arrays.sort(admin,cmp);
sum=admin[n-1].l;
long c=admin[n-1].l+admin[n-1].r;
for(int i=n-2;i>=0;i--) {
sum+=admin[i].l;
c=Math.max(c, sum)+admin[i].r;
}
out.println(c);
}
out.flush();
out.close();
}
}
class Ad{
int l;
int r;
int d;
}