开发工具:
文件大小: 158kb
下载次数: 0
上传时间: 2011-03-18
详细说明： 有两个序列a,b，大小都为n,序列元素的值任意整数，无序； 要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。 例如: var a=[100,99,98,1,2, 3]; var b=[1, 2, 3, 4,5,40]; 求解思路： 当前数组a和数组b的和之差为 A = sum(a) - sum(b) a的第i个元素和b的第j个元素交换后，a和b的和之差为 A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i]) = sum(a) - sum(b) - 2 (a[i] - b[j]) = A - 2 (a[i] - b[j]) 设x = a[i] - b[j] |A| - |A'| = |A| - |A-2x| 假设A > 0, 当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小， x越接近A/2效果越好, 如果找不到在(0,A)之间的x，则当前的a和b就是答案。 所以算法大概如下： 在a和b中寻找使得x 在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素， 重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。 ///////////////////////////////////////// 算法 1. 将两序列合并为一个序列，并排序，为序列Source 2. 拿出最大元素Big，次大的元素Small 3. 在余下的序列S[:-2]进行平分，得到序列max，min 4. 将Small加到max序列，将Big加大min序列，重新计算新序列和，和大的为max，小的为min。 //////////////////////////////////////////////// ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
