玩游戏

Posted on In

题目大意：Alice 和 Bob 在玩游戏。

数轴上有 𝑛 枚石子（ 𝑛 为偶数），每个位置上至多只有一枚石子。Alice 和 Bob 轮流把某个石子取走，Alice 先手，直至数轴上只剩下两枚石子。Alice 想要让这两枚石子的距离尽量小，而 Bob 则想让它们之间的距离尽量大。在双方都进行完美操作的情况下，最终剩下的两枚石子之间的距离会是多少呢？n属于1e5

最后一定只会剩下两个石头，其中女孩为了确保两个石头之间的距离最小，所以一定只会拿掉除了这两个石头之外的石头，而男孩为了确保两个石头之间的距离尽可能大，一定会拿掉这两个石头中间的石头

其中n为偶数，所以男孩拿的时候，一定会是中位数，就这样，我们只需要枚举最后剩下哪两个石头就好了，并且由上面的推理可以发现，这两个石头一定差着n/2，O(n)扫一遍就出结果了

我原来的思路：女孩一定是从两边拿石头，男孩一定是从拿中间距离最小的两个石头（错误）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef pair<int, int> pr;

const int N = 1e5 + 66, inf = 214748364;

int n;
int a[N];

signed main()
{
    int i;
    n = read();
    for (i = 1; i <= n; ++ i) a[i] = read();
    sort(a + 1, a + n + 1);
    int res = 1e9;
    for (i = 1; i <= n/2; ++ i) res = min(res, a[i + n/2] - a[i]);
    put(res);
    return 0;
}