P3507 [POI2010]GRA-The Minima Game

universehyf

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

3                                               2
1 3 1

universehyf

经典数学博弈论

universehyf

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cstdio>
   
4. using namespace std;
   
5. #define FOR(i,n,m) for(int i=n;i<=m;i++)
   
6. const int MX=1000010;
   
7. int n,a[MX],f;
   
8. int main()
   
9. {
   
10.     cin>>n;FOR(i,1,n) cin>>a[i];
    
11.     sort(a+1,a+n+1);
    
12.     FOR(i,1,n) f=max(f,a[i]-f);
    
13.     printf("%d",f);
    
14.     return 0;
    
15. }

复制代码