luogu2123 皇后游戏

据说这题是ltt出的?

题面

显然因为ai,bi>0a_i,b_i>0 ,所以最后一个人拿到的钱一定最多。

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

考虑两个人的情况,第一个人左手上为a1a_1,右手上为b1b_1,第二个人左手上为a2a_2,右手上为b2b_2

如果第一个人在前面,则第二个人拿到的钱数为max(a1+b1,a1+a2)+b2=a1+b2+max(b1,a2)=a1+b1+a2+b2min(b1,a2)\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(a2+b2,a2+a1)+b1=a2+b1+max(b2,a1)=a1+b1+a2+b2min(b2,a1)\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)

如果第一个人在前面,则a1+b1+a2+b2min(b1,a2)<a1+b1+a2+b2min(b2,a1)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(b2,a1)<min(b1,a2)\min(b_2,a_1)<\min(b_1,a_2)

多个人也可以这么考虑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
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;
}
文章目录
|