小X与游戏

hymcr052024-09-172024-12-15

题目描述

小X和小Y正在玩一个游戏，这个游戏是这样的：桌上放着n叠卡片，每叠恰好有两张。每张卡片有一个分数。小X为先手，双方轮流操作。轮到一方操作时，他可以选择取走某一叠卡片顶端的那一张（即：若这一叠还剩2张则取走上面的一张，否则取走下面的一张），并获得它的分数。他也可以选择不取。若卡片取完了、或者双方都选择不取卡片，那么游戏结束。
小X和小Y都希望自己的分数减去对方的分数尽可能大。现在假设小X和小Y都绝顶聪明，总是做出对自己最有利的决策，请算出游戏结束时小X比小Y高多少分。

输入
从文件 game.in 中读入数据。

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

输出
输出到文件 game.out 中。

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

样例输入
2
1 2
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和小y，他们绝顶聪明，题目原话：（现在假设小X和小Y都绝顶聪明，总是做出对自己最有利的决策，请算出游戏结束时小X比小Y高多少分。）

好，那么我们来先来讲讲样例：
小x先选：他选了4号于是x=4
小y再选：他选了3号于是y=4

因为他们绝顶聪明，所以，没有一个大笨蛋是选1号，然后把好2号的让给别人，于是被迫结束
那么输出x-y=1,于是答案就是1

因为题目说了，小x和小y只会做出最自己完全有利的决策

所以如果 a < b 时，是没有人会去第一个拿掉上面的牌的

接着，当 a = b 时，两人同时加上一个数，是没有意义的 x=y,a=b -> a + x = y + b
所以通过这样来筛选掉没有必要的牌堆

归纳一下
也就是a>b时，才可以使用这个牌堆
然后排序：把越大的排在越前，即体现出两个人每次都拿最大的
最后每个人拿就可以了

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int num[200003];//表示可以选择的数组 
int x, y, cnt;//x: 小x的数值
			  //y: 小y的数值 
bool cmp(int x, int y)
{
    return x > y;//排序 
}
main()
{
    cin >> n;//输入 
    for (int i = 1; i <= n; i++) { 
    	
        int a, b;
        cin >> a >> b;//还是输入 
        if (a > b) {//只有当a > b时才将 a , b 加入到可以选择的数组中
		/*因为题目说了，小x和小y只会做出最自己完全有利的决策
		  所以如果 a < b 时，是没有人会去第一个拿掉上面的牌的
		  接着，当 a = b 时，两人同时加上一个数，是没有意义的  x=y,a=b ->  a + x = y + b 
		  所以通过这样来筛选掉没有必要的牌堆 
		*/ 
            num[++cnt] = a;
            num[++cnt] = b; //加入可以选择的数组中
        }
    }
    sort(num + 1, num + 1 + cnt, cmp);//进行排序，把越大的排在越前，即体现出两个人每次都拿最大的 
    for (int i = 1; i <= cnt; i++) {
	//遍历可以选择的数组
        if (i % 2 != 0)/*判断是谁来取数 ，即：当i=1,3,5...小x取 
											  当i=2,4,6...小y取，也就是：奇数：小x，偶数：小y*/ 
            x += num[i];
        else
            y += num[i];
    }
    cout << x - y;
    return 0;
}