Codeforces Canada Cup 2016 F. Family Photos 博弈 策略分析 好题

题意：A和B博弈。有n个桶，每个桶里有两颗球，只能先拿走上面的球，再拿走下面的球，每颗球价值ai与bi，ai表示A拿走该球时获得的钱，bi表示B拿走该球时获得的钱。

游戏目的：A和B均想使比赛结束时自己的钱比对方的钱多尽量多。

每轮中，玩家可以选择拿球，或者不拿球，当一次轮换后A、B均选择不拿球，游戏结束。

输出双方都用最优策略时，游戏结束后A与B的钱差值。

解法：

其实，两人要么一直不断交替拿球，要么都停住，所以游戏可以看成双方不断拿球直到谁都不拿的过程。

先考虑简单的4种单桶情况：

1. a1<=b2 且 a2<=b1

谁先拿都不会有好处，且后拿一定不会亏本，所以两人都希望对方先拿，故该桶两人都不会拿。称其为废桶。

2. a1+b1<=a2+b2 且 a1>b2

A先拿好处少，后拿好处多，但是都有好处；B先拿坏处少，后拿坏处多，故B一定不会拿该桶，A只好先拿，即使好处比后拿少。称这种痛为先手桶。

3. a1+b1<=a2+b2 且 b1>a2

B先拿好处少，后拿好处多，但是都有好处；A先拿坏处少，后拿坏处多，故A一定不会拿该桶，B只好先拿，即使好处比后拿少。称这种桶为后手桶。

这种桶谁先拿都比后拿有好处，即賺多、亏少或化亏为賺。称这种桶为公共桶。

接下来合在一起考虑，废桶双方都不会拿走第一个球，故不考虑，先手桶先手可以等到最后再拿，因为后手不会抢着拿先手桶的第一个球；后手桶同理。所以双方会先拿公共桶里的球，且会按照每个球a+b从大到小的顺序拿，因为对于任何一个球，A拿走与B拿走，产生的价值差距就是a+b，故按从a+b由大到小的顺序拿，是最优策略。

当公共桶的球被拿光了之后，换成先手拿先手桶的第一个球，此时，后手一定得抢着拿走第二个球，而不是拿走自己后手桶的第一个球，将两个球对选择权交给先手。

代码如下：

#include <cstdio>#include <queue>using namespace std;typedef long long ll;int n;bool f;ll a1,a2,b1,b2,ra,rb;struct ss {    ll a,b;    ss(){}    ss(ll a,ll b):a(a),b(b){}    bool Operator>(const ss &s2)const{        return a+b<s2.a+s2.b;    }};PRiority_queue<ss,vector<ss>,greater<ss> > que;int main(){    scanf("%d",&n);    for (int i=0;i<n;++i) {        scanf("%lld%lld%lld%lld",&a1,&b1,&a2,&b2);        if (a1+b1<=a2+b2) {            if (a1>b2) {                ra+=a1;                rb+=b2;            } else if (b1>a2) {                ra+=a2;                rb+=b1;            }        } else {            que.push(ss(a1,b1));            que.push(ss(a2,b2));        }    }    while (!que.empty()) {        if (!f)            ra+=que.top().a;        else            rb+=que.top().b;        f=!f;        que.pop();    }    printf("%lld/n",ra-rb);    return 0;}
排序版本的：
#include <cstdio>#include <algorithm>using namespace std;const int maxn=200005;typedef long long ll;int n,c;ll a1,a2,b1,b2,ra,rb;struct ss {    ll a,b;    ss(){}    ss(ll a,ll b):a(a),b(b){}    bool operator<(const ss &s2)const{        return a+b>s2.a+s2.b;    }}pub[maxn];int main(){    scanf("%d",&n);    for (int i=0;i<n;++i) {        scanf("%lld%lld%lld%lld",&a1,&b1,&a2,&b2);        if (a1+b1<=a2+b2) {            if (a1>b2) {                ra+=a1;                rb+=b2;            } else if (b1>a2) {                ra+=a2;                rb+=b1;            }        } else {            pub[c++]=ss(a1,b1);            pub[c++]=ss(a2,b2);        }    }    sort(pub,pub+c);    for (int i=0;i<c;++i)        if (i&1)            rb+=pub[i].b;        else            ra+=pub[i].a;    printf("%lld/n",ra-rb);    return 0;}