題意：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;}