[原创]codeforces 594A Warrior and Archer [对称博弈]【博弈】

2016-09-07 13:38:21 Tabris_ 阅读数：699

博客爬取于2020-06-14 22:43:29
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52458744

题目链接:http://codeforces.com/problemset/problem/594/A
--------------------------------------------.
A. Warrior and Archer
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
In the official contest this problem has a different statement, for which jury’s solution was working incorrectly, and for this reason it was excluded from the contest. This mistake have been fixed and the current given problem statement and model solution corresponds to what jury wanted it to be during the contest.

Vova and Lesha are friends. They often meet at Vova’s place and compete against each other in a computer game named The Ancient Papyri: Swordsink. Vova always chooses a warrior as his fighter and Leshac chooses an archer. After that they should choose initial positions for their characters and start the fight. A warrior is good at melee combat, so Vova will try to make the distance between fighters as small as possible. An archer prefers to keep the enemy at a distance, so Lesha will try to make the initial distance as large as possible.

There are n (n is always even) possible starting positions for characters marked along the Ox axis. The positions are given by their distinct coordinates x1, x2, …, xn, two characters cannot end up at the same position.

Vova and Lesha take turns banning available positions, Vova moves first. During each turn one of the guys bans exactly one of the remaining positions. Banned positions cannot be used by both Vova and Lesha. They continue to make moves until there are only two possible positions remaining (thus, the total number of moves will be n - 2). After that Vova’s character takes the position with the lesser coordinate and Lesha’s character takes the position with the bigger coordinate and the guys start fighting.

Vova and Lesha are already tired by the game of choosing positions, as they need to play it before every fight, so they asked you (the developer of the The Ancient Papyri: Swordsink) to write a module that would automatically determine the distance at which the warrior and the archer will start fighting if both Vova and Lesha play optimally.

Input
The first line on the input contains a single integer n (2 ≤ n ≤ 200 000, n is even) — the number of positions available initially. The second line contains n distinct integers x1, x2, …, xn (0 ≤ xi ≤ 109), giving the coordinates of the corresponding positions.

Output
Print the distance between the warrior and the archer at the beginning of the fight, provided that both Vova and Lesha play optimally.

Examples
input
6
0 1 3 7 15 31
output
7
input
2
73 37
output
36
Note
In the first sample one of the optimum behavior of the players looks like that:

Vova bans the position at coordinate 15;
Lesha bans the position at coordinate 3;
Vova bans the position at coordinate 31;
Lesha bans the position at coordinate 1.
After these actions only positions 0 and 7 will remain, and the distance between them is equal to 7.

In the second sample there are only two possible positions, so there will be no bans.

--------------------------------------------.

题目大意：
大概就是在一个坐标轴上有N个点然后有两个人他们轮流去掉一个点知道最后剩下两个点为止
其中呢先手是希望最后剩下的两个点距离最大
后手是希望最后剩下的两个点距离最小
问的是最后剩下的两个点距离最小是多少

解题思路：
做这道题的时候只想到可能是博弈其他的一点想法都没有最后还是去查了题解发现这种问题属于对称博弈

对称博弈大概就是有两个个体无角色区分的人且有着相同的运动区间大致就这样

然后分析下这道题

转自这里
我们假设最后留下来的位置是l和r。

接下来我们要证明l和r之间的距离一定是n/2 - 1！

首先我们证明距离不会大于n/2 - 1。

假设距离 > n/2 - 1，那么显然Warrior肯定在其中选了一个位置。但是如果Warrior这么做，他完全可以放弃这个位置，去选L或者R，这样就能缩短最终距离。所以这种情况不可能。
既然如此，那么距离肯定是 <= n/2 - 1。Archer只能努力让距离保持在n/2 - 1。
Warrior的最优选择肯定是选择最左端或者最右端的空，Archer总是选剩下能选择的空里的中间那个空，所以到最后[L, R]之间Archer肯定能选择n/2 - 1步，也就是距离肯定是 n/2 - 1。

所以最终R - L = n / 2

于是乎这道题就能解了。。。

附本题代码
-------------------------------.

# include <bits/stdc++.h>
using namespace std;
typedef long long int LL ;
# define INF 0x3f3f3f3f

int a[201010];
int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];

    sort(a,a+n);

    int ans = INF;
    for (int i = 0; i + n/2 < n; i++)
        ans = min(ans, a[i+n/2] - a[i]);
    cout<<ans<<endl;

    return 0;
}