华为面试题华为面试题华为面试题
3星 · 超过75%的资源 需积分: 35 81 浏览量
2009-10-12
15:01:20
上传
评论 7
收藏 48KB DOC 举报 
传说这是一道华为的面试题。。。。
/*******************************************************************
文件名: 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