「题解」「POI2010」GRA-The Minima Game

题目链接:Luogu P3507

题目

题意简述

给出 $N$ 个正整数,Alice 和 Bob 两个人轮流取数,Alice 先取。每次可以取任意多个数,直到 $N$ 个数都被取走。每次获得的得分为取的数中的最小值,Alice 和 Bob 的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下,最终 Alice 的得分减去 Bob 的得分为多少。

数据据范围

$$1\leq n\leq 10^6,1\leq k_i\leq 10^9$$

题解

思路

显然,我们知道,对于 Alice 和 Bob,他们取数必然是取排序后连续的一段,不会随便乱取(因为取得的最小值是得分,这样会使得得分变少)。

所以,我们先对原数组排序(从小到大排序后第 $i$ 个元素设为 $a_i$)我们可以设 $f_i$ 表示取了 $i$ 个数后的最大得分。

那么得出状态转移方程:

$$f_i=\max_{(0\leq j\leq i-1)}{a_j-f_j}$$

这里存在一个 $j$ 的枚举过程使得算法的时间复杂度为 $\Theta(n^2)$。

化简发现:

$$f_i=\max{f_{i-1},a_{i-1}-f_{i-1}}$$

这个状态转移方程对应的动态规划的时间复杂度为 $\Theta(n)$,可以通过。

代码

代码比较简单没什么好说的,算上排序的时间复杂度,总的时间复杂度为$\Theta(n\log_2n)$。

#include<cstdio>
#include<algorithm>
using std::max;
using std::sort;
//以上是头文件
const int MAXN=1000000+5;//数据范围最大值
int n;
int a[MAXN];
int f[MAXN];//动态规划数组
int main(void){
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);//排序
    for(i=1;i<=n;++i)
        f[i]=max(f[i-1],a[i]-f[i-1]);//状态转移方程
    printf("%d\n",f[n]);//输出答案
    return 0;
}