小X与游戏（策略）

小X与游戏

时间限制: 1 Sec 内存限制: 128 MB

题目描述

小X和小Y正在玩一个游戏，这个游戏是这样的：桌上放着n叠卡片，每叠恰好有两张。每张卡片有一个分数。小X为先手，双方轮流操作。轮到一方操作时，他可以选择取走某一叠卡片顶端的那一张（即：若这一叠还剩2张则取走上面的一张，否则取走下面的一张），并获得它的分数。他也可以选择不取。若卡片取完了、或者双方都选择不取卡片，那么游戏结束。

小X和小Y都希望自己的分数减去对方的分数尽可能大。现在假设小X和小Y都绝顶聪明，总是做出对自己最有利的决策，请算出游戏结束时小X比小Y高多少分。

输入

输入的第一行包含一个正整数n。
接下来n行，每行包含2个用空格隔开的非负整数a[i], b[i]，分别表示第i叠中放在上面、下面的卡片的分值。

输出

输出仅有一行包含一个整数，表示游戏结束时小X比小Y高多少分。如果小X的分数比小Y低则输出一个负数。

样例输入

复制样例数据

2
1 2
4 3

样例输出

提示

样例解释
小X取走4，小Y取走3，小X不取，小Y不取，游戏结束。4-3=1

数据范围
对于30%的数据，1<=n<=1000, b[i]=0
对于70%的数据，1<=n<=1000
对于100%的数据，1<=n<=100000, 0<=a[i], b[i]<=1000000

首先得搞懂最优策略什么。

策略：如果轮到小X选择，那么肯定选择所有叠的顶端的最大数，并且，如果那张牌底下有一张比它大的牌，那么这一叠牌是不会选的。假设全选前小X与小Y相差a，如果小X选择了那一叠（假设上面为x,下面为y且y>x且x为），那么加上这个数x，那么轮到小Y选择，肯定会选择y,那么差会缩小y-x，这是小X不愿看到的，所以这一叠是不会选择的。小Y选择也是同理。。

PS:可能会有a[i]相同的情况，如果是小X选择a[i]，那么会优先考虑b[i]小的，这样可能会使小Y加的更少。。。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;

struct node
{
	int x, y;
	bool operator <(const node &a)const{
		return x == a.x ? y > a.y : x < a.x;
	}
}a;

priority_queue<node> q;//优先队列维护最大值

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%d %d", &a.x, &a.y);
		q.push(a);
	}
	LL ans = -(1LL << 60), sum1 = 0, sum2 = 0;//注意ans的范围和初始化的值
	int num = 0;
	while(q.size()){
		node t = q.top();
		q.pop();
		if(t.y > t.x) continue;//如果下面的牌比上面的大，不要选
		if(num & 1){//小Y选择
			sum2 += t.x;
			ans = max(ans, sum1 - sum2);//一个轮回更新下差
		}else{//小X选择
			sum1 += t.x;
		}
		if(t.y != -1) t.x = t.y, t.y = -1, q.push(t);//如果选择了a[i]，那么b[i]代替a[i],b[i]设为尽量小的值(<0)
		num++;
	}
	ans = max(ans, sum1 - sum2);//有可能小Y没有选择，也要更新下值
	printf("%lld\n", ans);

	return 0;
}
/**/