The Minima Game bzoj-2091 Poi-2010

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

注释：$1\le n\le 10^6$。

想法：显然从大到小依次选。

之后暴力地dp，根本意义上是一种模拟贪心。

Code：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 1000010

using namespace std;

int a[N];

int main()

{

	int n; cin >> n ; for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	sort(a+1,a+n+1); int x=0;

	for(int i=1;i<=n;i++) x=max(a[i]-x,x);

	cout << x << endl ;

	return 0;

}

小结：水题。

巴特西

[bzoj2091][Poi2010]The Minima Game_动态规划

The Minima Game bzoj-2091 Poi-2010

最新文章

热门文章