蓝桥杯练习题二 - 合并检测（c++）

题目如下

新冠疫情由新冠病毒引起，最近在 A 国蔓延，为了尽快控制疫情，A 国准 备给大量民众进病毒核酸检测。

然而，用于检测的试剂盒紧缺。为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（k 个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 k 个人都是阴性，用一个试剂盒完成了 k 个人的检测。如果结果为阳性，则说明 至少有一个人为阳性，需要将这 k 个人的样本全部重新独立检测（从理论上看， 如果检测前 k−1 个人都是阴性可以推断出第 k 个人是阳性，但是在实际操作中 不会利用此推断，而是将 k 个人独立检测），加上最开始的合并检测，一共使用 了 k + 1 个试剂盒完成了 k 个人的检测。

A 国估计被测的民众的感染率大概是 1%，呈均匀分布。请问 k 取多少能最节省试
剂盒？

以下程序实现了这一功能，请你补全以下空白处内容：

#include 
int main()
{
    double m = 4537;
    double min = 9999999;
    double k, sum, ans;
    for (k = 1; k <= 100; k++)
    {
        sum = (m - k) / k + 0.01 * m * k + 1;
        __________________;
    }
    printf("%d\n", (int)ans);
    return 0;
}

提示：
设检测人数为100人，根据概率为1%，则只有1个为阳性。k个人一组，则需要的试剂数量
为：对所有分组进行合并检测所需要的试剂数100/k+其中1个分组阳性所需要的试剂数k+
未分组人数所需的试剂数量。 

其实题中已经给出了部分代码，不过博主个人认为这个解题思路有点理解不了，很难让人明白为什么要这么做，有兴趣的同学可以顺着这个思路想下去，欢迎评论区讨论。

今天博主的思考方式略微有些不同，咱们先看看代码，然后根据代码，一步步给大家解析思路，最终达到理解的程度：

#include 
using namespace std;
int main()
{ 
  /*
      检测总人数，我们假定一个值，也可以设置的更大，但其实没这个必要，想改值的也
      可以试试，结果不出意外应该都一样
  */
  double m = 4537;
  /*
      每组人数最小值，这里设置一个绝对大的值，但肯定用不上，一组绝对不会这么多人，
      作用是方便我们做比较的时候设置最小值
  */
  double min = 99999; 
  /*
      这里的三个值是我们需要用到来计算的，不得不叹息一声，数学才是万能的啊
      k:每次合并检测的人数
      sum:所需试剂盒数
      ans:最优k的解
  */
  double k, sum, ans; 
  /*
    循环，直至找到最优解，k设置100是因为一组绝对不会100人，代价太大，我们
    现实中检测也不过就是10人一组，因为一旦有一个人感染，那么必须一个人一个
    试剂盒，绝对的浪费
  */ 
  for (k = 1;k < 100;k++)
  {
        /*
            这里是总人数整除每组人数取余，如果刚好除尽，这么多人首次检测就只需
            要m/k个试剂盒
        */
      if ((int)m % (int)k == 0)
      {
            /*
                m/k是首次检测这么多人需要的试剂盒，0.01*m是出现感染人的数量，
                因为感染人是平均分布的，所以可以认为有0.01*m的分组中，每组存
                在一个感染者，需要对这些组的每一个人进行单独的检测，每组人数为k，
                则二次检测需要0.01*m*k个检测盒，加起来就是一共的检测数
            */
          sum = m / k + 0.01 * m * k;
      }
      else
      {
          /*
              这里和上面是一样的道理，因为除不尽，所以需要额外增加一个检测盒，
              不过这里有个特殊情况，如果被感染者刚好存在于最后这个不足k人的
              分组中，这一组总检测试剂盒数是不足k的，但是这种情况被忽略了，
              原因是，即使不足k人，差距也不过就是几个，跟全体比起来微不足道，
              这样的分组一般也存在极少数，所以这种极低概率事件在这种大数量检
              测情况下可以忽略不计。（同学们切不可钻牛角尖，“大局为重”）
          */
          sum = m / k + 0.01 * m * k + 1;
      }
      //看这里，min派上用场了
      if (sum < min)
      {
          //min=sum，所以每一次都取到的是sum（总试剂盒）的最小值
          min = sum;
          //最小值对应的k就是最佳每组人数
          ans = k;
      }
  }
  /*
      最后输出最佳人数，为10，果然和我们现实中检测是一样的，厉害了，再次感叹，
      算法来源于数学，数学牛逼
  */
  cout << ans << endl;
  return 0;
}

注释写的非常清楚了同学们，仔细看就一定能理解这个算法，个人认为要比原题目中那种思路要容易理解的多。

 最后，有什么不理解的欢迎评论区留言讨论！