P3507 [POI2010]GRA-The Minima Game

题目描述

Alice and Bob learned the minima game, which they like very much, recently.

The rules of the game are as follows.

A certain number of cards lies on a table, each inscribed with a positive integer.

The players make alternate moves, Alice making the first one.

A move consists in picking an arbitrary positive number of cards from the table.

For such move the player receives a number of points equal to the minimum of the numbers inscribed on the cards he collected.

The game ends when the last card is removed from the table.

The goal of each player is maximizing the difference between their and their opponent's score.

Alice and Bob have duly noted that there is an optimal strategy in the game.

Thus they are asking you to write a program that, for a given set of cards, determines the outcome of the game when both players play optimally.

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

输入输出格式

输入格式：

In the first line of the standard input there is one integer  () given, denoting the number of cards.

The second line holds  positive integers  (), separated by single spaces, that are inscribed on the cards.

输出格式：

Your program should print out a single line with a single integer to the standard output - the number of points by which Alice wins over Bob, assuming they both play optimally; if it is Bob who has more points, the result should be negative.

输入输出样例

3
1 3 1

2

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=12700000;
 7 inline void read(int &n)
 8 {
 9     char c=getchar();n=0;bool flag=0;
10     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
11     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
12 }
13 int a[MAXN];
14 int n;
15 int main()
16 {
17     int n;read(n);
18     int MAX=-1,MIN=0x7fff;
19     for(int i=1;i<=n;i++)    read(a[i]);
20     sort(a+1,a+n+1);
21     int ans=0;
22     for(int i=1;i<=n;i++)
23         if(ans<a[i]-ans)    
24             ans=a[i]-ans;
25     printf("%d",ans);
26     return 0;
27 }

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有