[博弈 + 结论] AtCoder ARC094E. Tozan and Gezan

思维题,要想全面。

若某个时间 \(A_i < B_i\) ,则这个位置一定会被拖到 \(A_i=B_i=0\)\((A_i,B_i)\) 等价于 \((0,B_i-A_i)\)

想清楚后可以发现,玩家 \(2\) 实际上什么都干不了,

\(A_i>B_i\) 时,减小 \(B_i\) 不会对自己更优,只能放着不动,当玩家 \(1\) 不断减小 \(A_i\) ,使 \(A_i<B_i\) 时,就垮掉了....

玩家 \(1\) 可以不断减那些 \(A_i>B_i\) 的位置,使 \(A_i<B_i\) ,同时要注意过程中不能都相等。

分析一下可以发现,玩家 \(1\) 可以做到最后只留一个不为 \(0\) ,取最小的的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,flg,_min=2e9;
LL ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y; scanf("%d%d",&x,&y);
ans+=y;
if(x>y) _min=min(_min,y);
if(x!=y) flg=1;
}
printf("%lld\n",flg?ans-_min:0);
return 0;
}