本文共 544 字,大约阅读时间需要 1 分钟。
题目描述:
有两个序列a,b,大小都为n,序列元素的值任意整数,无序;
要求:通过交换a,b 中的元素,使[序列a 元素的和]与[序列b 元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
分析:
很多情况下,贪心算法得到的解并不是最优解,但是这道题貌似是最优解
思想:每次从AB中找到两个使得和之差最小的元素交换
当前和之差diff=sumA-sumB,从A中找到一元素a,从B中找到一元素b,如果交换那么就须有(sumA-a+b)-(sumB-b+a)=sumA-sumB-2(a-b)=diff-2(a-b),
也就是使得abs(diff-2(a-b))最小的值交换
#include "iostream" #include#include #include using namespace std;#define N 6int A[N]={100,99,98,1,2,3};int B[N]={1,2,3,4,5,40};void Swap() { int sumA=0,sumB=0; for (int i=0;i
转载地址:http://qdvvi.baihongyu.com/