抽签问题

你的朋友提议玩一个游戏:将写有数字的 n 个纸片放入口袋中，你可以从口袋中抽取 4 次纸 片，每次记下纸片上的数字后都将其放回口袋中。如果这 4 个数字的和是 m，就是你赢，否 则就是你的朋友赢。你挑战了好几回，结果一次也没赢过，于是怒而撕破口袋，取出所有纸 片，检查自己是否真的有赢的可能性。请你编写一个程序，判断当纸片上所写的数字是时，是否存在抽取 4 次和为 m 的方案。如果存在，输出 Yes;否则，输出 No。

限制:

解法一

四重循环暴力搜索

解法二

最内层循环要做的是检查是否有使得
等价于检查数组中是否存在满足
即检查数组中所有元素，判断是否有

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
// #define 关键字在C/C++中用作宏处理,基本作用如下, 宏定义不要以分号结尾
#define MAX_MN 1000000
int n=3, m=9, k[MAX_MN]={1,3,5};
string solve() {
  sort(k, k+n);
  string ans = "false";
  for (int a=0; a<n; a++) {
    for (int b=0; b<n; b++) {
      for(int c = 0; c<n; c++) {
        if (binary_search(k, k+n, m-k[a]-k[b]-k[c])) {
          ans = "true";
          break;
        }
      }
    }
  }
  return ans;
}
int main() {
  cout << solve() << endl;
  return 0;
}

解法三

本质上还是以空间换时间

在内层的两个循环中找到,先用一个数组存储,然后再在该数组中进行二分查找

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
// #define 关键字在C/C++中用作宏处理,基本作用如下, 宏定义不要以分号结尾
#define MAX_MN 1000
int n=3, m=9, k[MAX_MN]={1,3,5};
string solve() {
  int kk[MAX_MN * MAX_MN];
  string ans = "false";
  for (int c=0; c<n ; c++) {
    for (int d=0; d<n; d++) {
      kk[c*n+d] = k[c] + k[d];
    }
  }
  sort(kk, kk + n*n);
  for (int a=0; a<n;a++) {
    for (int b=0; b<n; b++) {
      if (binary_search(kk, kk+n*n, m-k[a]-k[b])) {
        ans = "true";
        break;
      }
    }
  }
  return ans;
}
int main() {
  cout << solve() << endl;
  return 0;
}