[13]纸牌游戏-腾讯2018秋

1.题目描述

牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌,第i张纸牌上写着数字ai。牛牛和羊羊轮流抽牌,牛牛先抽,每次抽牌他们可以从纸牌堆中任意选择一张抽出,直到纸牌被抽完。他们的得分等于他们抽到的纸牌数字总和。
现在假设牛牛和羊羊都采用最优策略,请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。

• 输入描述:
  输入包括两行。
  第一行包括一个正整数n(1<=n<=105),表示纸牌的数量。
  第二行包括n个正整数ai(1<=ai<=109),表示每张纸牌上的数字。
• 输出描述:
  输出一个整数,表示游戏结束后牛牛得分减去羊羊得分等于多少。
• 输入示例：

  3 
  2 7 4
  

• 输出示例：

  5
  

2.题目解析

抽牌最优策略，就是先抽牌中最大的值。

3.参考答案

#include <bits/stdc++.h>
using namespace std;

int cmp(int a,int b){
    return a > b;
}
int main() {
   int n = 0;
   scanf("%d",&n);
   int nums[n];
   fill_n(nums,n,0);
   for(int i=0;i<n;++i){
       scanf("%d",&nums[i]);
   }
   sort(nums,nums+n,cmp);
   int niuniu = 0;
   int yangyang = 0;
   for(int i=0;i<n;++i){
       if(i%2==0){
           // niuniu = niuniu+ nums[i];
           niuniu += nums[i];
       }else{
           yangyang += nums[i];
       }
   }
   printf("%d\n",niuniu-yangyang);

   return 0;
}

#include <bits/stdc++.h>
using namespace std;

int cmp(int x, int y) { return x > y; }
int main() {
  int n = 0;
  scanf("%d", &n);
  int a[n];
  for (int i = 0; i != n; ++i)
    scanf("%d", &a[i]);
  
  // 排序
  sort(a, a + n, cmp);

  // 遍历
  int res = 0;
  for (int i = 0; i != n; ++i) {
    if (i % 2 == 0) { // 牛牛抽牌
      res += a[i];
    } else { // 羊羊抽牌
      res -= a[i];
    }
  }
  printf("%d\n",res);
  return 0;
}

牛客题目