「题解」P3507|GRA-The Minima Game

题意

洛谷原题面

给 $N$ 个正整数，$A,B$ 轮流取任意多个数，直到取完。每次得分为取的数中的最小值，$A,B$ 都尽可能使得自己的得分减去对手的得分更大，求 $A$ 与 $B$ 得分的差值

数据范围：$1\leq n\leq 10^6 ,1\leq k_i \leq 10^9$

思路

有几个需要想通的地方：

• 得分为取数中的最小值。假设我们想要的得分为 $x$，那么显然我们需要把大于 $x$ 的数全部选中，否则会给对手得到更大得分的机会。

• 两人一定从大到小取数。若 $A$ 不从大往小取，那么 $B$ 取了大的数，$A$ 就吃亏了。

在这么多种方案中，如何决策那个要取的数 $x$ ，我们考虑动态规划。先将数组从小到大排序，根据上面的推理，我们将 $f[i]$ 定义为当前操作者从 $i$ 向前取出现的最佳方案

枚举每一个 $i$，对于 $f[i]$ 枚举 $j(1\leq j\leq i)$，$A$ 先手控制 $i$ 到 $j$，$B$ 再控制 $1$ 到 $j-1$ 中出现的最佳方案，寻找其中的最大值。状态转移方程为

$f[i]=\max(a[j]-f[j-1])$

但是数据范围不允许 $O(n^2)$ 复杂度，需要优化，我们展开 $f[i]$ 和 $f[i-1]$

$f[i]=\max(a[i]-f[i-1],a[i-1]-f[i-2],a[i-2]-f[i-3],\cdots ,a[1]) \\ \ \ \\ f[i-1]=\max(a[i-1]-f[i-2],a[i-2]-f[i-3],\cdots ,a[1])$

显然 $f[i]$ 后面几项等价于 $f[i-1]$，可以得到 $f[i]=\max(f[i-1],a[i]-f[i-1])$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N=1e6+9;
int n;
ll a[N],f[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) f[i]=max(f[i-1],a[i]-f[i-1]);
    printf("%lld",f[n]);
    return 0;
}