# 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.

## 输入输出格式

In the first line of the standard input there is one integer n(1<=n<=1000000) given, denoting the number of cards. The second line holds n positive integers k1,k2,...,kn(1<=ki<=10^9) 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`

f[i]表示剩下了1..i这个前缀的max(先手-后手)。

a[j]-f[j-1]的前缀max是很好维护的。

``` 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 {
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 }```

0 条评论

• ### HDU 3032 Nim or not Nim?(Multi-Nim)

Problem Description Nim is a two-player mathematic game of strategy in which ...

• ### POJ2409 Let it Bead(Polya定理)

"Let it Bead" company is located upstairs at 700 Cannery Row in Monterey, CA. As...

• ### 使用 PInvoke.net Visual Studio Extension 辅助编写 Win32 函数签名

2018-07-21 14:35

• ### hduoj-----(1068)Girls and Boys(二分匹配)

Girls and Boys Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/3...

• ### CodeForces 670C Cinema(排序，离散化)

C. Cinema time limit per test 2 seconds memory limit per test 256 megabyte...

• ### HOJ Recoup Traveling Expenses(最长递减子序列变形)

A person wants to travel around some places. The welfare in his company can cov...

• ### 【Codeforces】1213B - Bad Prices

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### Connecting language and knowledge with heterogeneous representations for neural relation extraction

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

Railroad Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (...