传说这是一道华为的面试题。。。。
/*******************************************************************
文件名: 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.ynutx.net
E-mail: DL88250@gmail.com
QQ: 845765 or 316281008
*******************************************************************/
#i nclude <ctime>
评论1