2012年华为校园招聘面试笔试题.docVIP

传说这是一道华为的面试题。。。。 /******************************************************************* 文件名: MinDifference(AVG).cpp 问题描述: 有两个数组a、b，大小都为n，数组元素的值任意，无序； 通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小， 最后输出两个数组和数组元素和的差值 解决思路：采用动态规划思想。先求出一个规划目标的模糊值AVG，表示“完美”的a与b的 情况：a的元素和sa与b的元素和sb相等，并都等于AVG。然后重置a与b：交换 a与b中的元素，另a中存有最小的n个元素（此时sa必然大于AVG）。b中存有 最大的n个元素（此时sb必然大于AVG）； 开始进行“完美逼近”规划：在一次a[k]与b[0...n-1]的循环中进行交换，使 得此时的sa逼近AVG（此时的sb也在逼近AVG）。在此过程中，如果sa与AVG相 等，这就产生了“完美”数组a与b，保证sa与sb的差值为0。如果到a[n-1] 时sa与AVG不等，不过此时的数组a和b已经能保证sa与sb的差值最小了 正确性证明：（用反证法易证之） 时间复杂度分析：O(n^2) 关键步骤：Step 0：合并数组a和b到数组c，并对c按升序排序； Step 1：求出数组c元素的和，除以2，其值为AVG； Step 2：将数组c里前n个数设置为数组a，后n个数设置为数组b， 并分别求出a元素与b元素的和，放入sa和sb； Step 3：设置整型计数器 i = 0； Step 4：a[i]与b[n-i-1]对换，并计算此时的sa与sb；//（试探） Step 5：如果sa大于AVG，a[i]与b[n-i-1]并重新算计sa与sb；//（回溯） Step 6：否则（sa小于AVG时）分别按升序排序a和b； Step 7：i++； Step 8：如果 i n，执行Step 4； Step 9：一次“逼近”过程结束； 开发平台: Win Xp SP2 编译环境: CL.exe 8.0 (in Visual Studio 2005 SDK) 作者: 88250 完成日期: 2006-11-26 版本: 2.0 修改之处：1. 修正了算法设计思想的描述：将贪心+回溯改为动态规划 2. 修正了存在重复比较数组a和b元素的问题，大大提高了处理效率 3. 可以从负值到正值地设定了数组元素的随机范围 Blog: http://DL88250. E-mail: DL88250@ QQ: 845765 or 316281008 *******************************************************************/ ＃i nclude ctime ＃i nclude vector ＃i nclude algorithm // 使用快速排序 ＃i nclude iterator ＃i nclude iostream #define TEST 0 // 测试开关 using namespace std; // 全局数组描述： const int num_max = 100; // 最大数组容量 const int range_min = -10; // 给定数组元素的最小值 const int range_max = 10; // 给定数组元素的最大值 vectorint a; // 数组a vectorint b; // 数组b vectorint c; // 数组c int average = 0; // 即算法描述中的AVG int sa = 0, sb = 0; // 分别保存数