c++奥赛题望解答！@#￥%

Question

小可很喜欢玩卡牌游戏，这天他想升级一下“达芬奇密码”游戏，假设一共有n张纸牌，要把这n张牌分给两个人，每个人手里的牌数不一定相同，只需要满足两个人手中的差尽可能小就可以。请编写程序分牌，并求出两组牌数字和的最小差1是多少

输入格式
第一行一个整数n，表示有n张牌（n<=20）
后面的n行，每行表示一张牌上的数字 xi（0<=xi<10的9次方）

输出格式
输出一个数，表示对应的最小差值

输入样例
3
2
2
3

输出样例
1

Answer 1

急！！！！！

Answer 2

核心思路
先假设钱全部在玩家1:(sum1)手里
然后玩家2每一轮循环去玩家1手里尝试取一张票票~
尝试的方式是求该轮取哪张票票,可以使得解最优(当前差值最小)
如果该轮没解,表示当前已为最优情况,可以跳出循环啦！
别忘了取过的票票要做标记哦 ^_^

#include<iostream>
using namespace std;
int main()
{
    int n,nums[21],sum1=0,sum2=0,key;
    cin >> n;
    for(int z=0;z<n;z++) {
        cin >> nums[z];
        sum1 += nums[z];
    }

    bool appear[21] = {false}; // 判断这个下标的数给2号玩家了没
    bool change = true;            // 判断有无发生变换,无变化说明已经最大
    while (change){

        int flag = -1;
        for(int z=0;z<n;z++){
            if(appear[z]) continue;
            if(flag!=-1)  key = abs(sum1-sum2-nums[z]*2+nums[flag]*2);
            else key = abs(sum1-sum2-nums[z]*2);
            if(abs(sum1-sum2)>key){
                if(flag!=-1) sum2 -= nums[flag]*2;
                flag = z;
                sum2 += nums[z]*2;
            }
        }
        if(flag==-1) change = false;
        else
        {
            appear[flag] = true;
            sum2-=nums[flag];
            sum1-=nums[flag];
        }
    }
//    cout << sum1 << ' ' << sum2 << endl;
    cout << abs(sum1-sum2) << endl;
    return 0;
}

Answer 3

有很多介绍"达芬奇密码”游戏的规则的，例如这篇，先从现实中存在的“达芬奇密码”游戏中了解规则后，再结合题中所给背景，如何实现尽可能的最小，可以借助线性表以及贪心、DP的思想来进行解决。

【达芬奇密码】游戏规则 适合2-4个人玩的桌游 https://baijiahao.baidu.com/s?id=1704536043813769829

Answer 4

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

double search(const std::vector<int> &nums, const std::vector<int> &a,
              const std::vector<int> &b) {
  if (nums.empty()) {
    auto sa = std::accumulate(a.begin(), a.end(), 0);
    auto sb = std::accumulate(b.begin(), b.end(), 0);
    return std::abs(sa - sb);
  }

  auto n1 = nums;
  auto x = n1.back();
  n1.pop_back();

  auto a1 = a;
  a1.push_back(x);
  auto s1 = search(n1, a1, b);

  auto b1 = b;
  b1.push_back(x);
  auto s2 = search(n1, a, b1);

  return std::min(s1, s2);
}

int main() {
  int n, x;
  std::vector<int> nums, a, b;
  std::cin >> n;
  for (int i = 0; i < n; i++) {
    std::cin >> x;
    nums.push_back(x);
  }
  std::cout << search(nums, a, b);
  return 0;
}