华师一附中OI组

标题: P3507 [POI2010]GRA-The Minima Game [打印本页]
作者: universehyf    时间: 2018-10-21 20:43
标题: P3507 [POI2010]GRA-The Minima Game
给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下，最终A的得分减去B的得分为多少。

3                                               2
1 3 1

作者: universehyf    时间: 2018-10-21 20:43
经典数学博弈论
作者: universehyf    时间: 2018-10-21 20:44
本帖最后由 universehyf 于 2018-10-25 21:31 编辑
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2