luogu2123 皇后游戏

题面

显然因为\(a_i,b_i>0\) ，所以最后一个人拿到的钱一定最多。

所以只需要考虑最后一个人拿到的钱数即可。

考虑两个人的情况，第一个人左手上为\(a_1\)，右手上为\(b_1\)，第二个人左手上为\(a_2\)，右手上为\(b_2\)。

如果第一个人在前面，则第二个人拿到的钱数为\(\max(a_1+b_1,a_1+a_2)+b_2=a_1+b_2+\max(b_1,a_2)=a_1+b_1+a_2+b_2-\min(b_1,a_2)\)。

反之第一个人拿到的钱数则为\(\max(a_2+b_2,a_2+a_1)+b_1=a_2+b_1+\max(b_2,a_1)=a_1+b_1+a_2+b_2-\min(b_2,a_1)\)

如果第一个人在前面，则\(a_1+b_1+a_2+b_2-\min(b_1,a_2)<a_1+b_1+a_2+b_2-\min(b_2,a_1)\)

可以变为\(\min(b_2,a_1)<\min(b_1,a_2)\)

多个人也可以这么考虑。

/*
Author: CNYALI_LK
LANG: C++
PROG: 2123.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
    ll cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
    putchar(end);
}
struct dachen{
    ll a,b; 
};
dachen a[102424];
ll ac(dachen a,dachen b){
    return min(a.a,b.b)<min(a.b,b.a);
}
int main(){
#ifdef cnyali_lk
    freopen("2123.in","r",stdin);
    freopen("2123.out","w",stdout);
#endif
    ll t,n;
    t=read();
    while(t){
        --t;
        n=read();
        for(ll i=1;i<=n;++i){
            a[i].a=read();a[i].b=read();
        }
        sort(a+1,a+n+1,ac);
        ll c=0,as=0;
        for(ll i=1;i<=n;++i){
            as+=a[i].a;
            chkmax(c,as);
            c+=a[i].b;
        }
        printf("%lld\n",c);
    }

    return 0;
}