科大讯飞2018暑期实习招聘在线编程题：如何分糖果？

题目描述&＃xff1a;小明和小红是好朋友&＃xff0c;但最近遇到一个棘手的问题&＃xff0c;有一盒糖果要分成两份但是每颗糖果质量都不尽相同&＃xff0c;但为了分配的公平每份糖的糖果数量相差不得超过1&＃xff0c;在此条件下两份糖果的质量差距尽可能小。

输入&＃xff1a;一行数&＃xff0c;包含一个数n&＃xff0c;代表糖果数量&＃xff0c;后面一次是n个整数一次表示每个糖果的质量&＃xff0c;每个糖果的质量都是1到450之间的一个整数&＃xff0c;每盒最多有20个糖果。

输出&＃xff1a;每个样例输出两个数字分别为两堆糖果的质量&＃xff0c;如不相同&＃xff0c;先小后大。

样例

输入&＃xff1a;5 9 6 5 8 7

输出&＃xff1a;17 18

一开始做这道题的时候&＃xff0c;我纠结于“找到一个策略&＃xff0c;按照这个策略分糖果就能得到结果”。但后来我发现&＃xff0c;其实根本不需要找出这么个策略&＃xff0c;只需用暴力搜索算法即可。关键点是&＃xff1a;“每份糖的糖果数量相差不得超过1”&＃xff0c;假设糖果数目是n&＃xff0c;则分成的两堆糖果的数量一定是n/2和n-n/2。这就归结为一个组合问题&＃xff1a;“如何在n个糖果中选n/2个糖果&＃xff0c;使得选出的糖果堆和剩下的糖果堆质量之差最小&＃xff1f;”

因此&＃xff0c;只要搜索所有C(n,n/2)种分糖方法&＃xff0c;就能找出差值最小的那种。

这里重点解释下search函数&＃xff1a;

第一个参数sugers&＃xff0c;表示所有糖的质量。

第二个参数weight&＃xff0c;表示当搜索到这一步时&＃xff0c;已经选取出来的糖果的质量总和。

第三个参数start&＃xff0c;表示“决定要不要选”的那颗糖果在sugers中的编号。

第四个参数count&＃xff0c;我手里这堆糖果中糖果的数量。如果count到达了n/2&＃xff0c;表明搜索到一种分法&＃xff0c;可以进行比较了。

第五个参数res&＃xff0c;表示“当前搜索过的所有分法中最好的分法”&＃xff0c;当搜索完后&＃xff0c;就是结果。

第六个参数target&＃xff0c;是糖果的总重量/2。

第七个参数minchazhi&＃xff0c;表示“当前搜索过的所有分法中最好的分法与target的差值”&＃xff0c;是分法好坏的依据。

最后两个&＃xff0c;sum是糖果的总重量&＃xff0c;n是糖果的总数。

#include
#include
#include
#include
#includeusing namespace std;void search(const vector &sugers, int weight, int start, int count, int &res,int target,int& minchazhi,int sum,int n)
{//用搜索法//我自己在糖果堆中选糖果&＃xff0c;对于每一颗糖果&＃xff0c;我可以选或者不选//如果选&＃xff0c;count&＃43;1&＃xff0c;表示我当前手里的糖果的数量//每次选完&＃xff0c;我手里的糖果达到总数量的一半后&＃xff0c;就进行手里糖果重量与总质量一半的最小差值minchazhi的更新//并记录在当前最小差值下的我手里糖果的质量,最后的res就是结果if (count &＃61;&＃61; n/2) {if (abs(2 * weight - sum) }int main()
{int n;while (cin >> n) {vector sugers(n);int sum &＃61; 0;for (int i &＃61; 0; i > sugers[i];sum &＃43;&＃61; sugers[i];}int target &＃61; sum / 2;int res &＃61; 0, minchazhi &＃61; INT_MAX;search(sugers, 0, 0, 0,res,target,minchazhi,sum,n);if(res>sum-res) cout <}