2019-12-26

有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
只能想到最傻的办法
感谢原作者，
https://blog.csdn.net/zengbo1019/article/details/25833515

python 3 代码

import random
import time
def timeit(func):
    def _deco(*args, **kwargs):
        start = time.perf_counter()
        m = func(*args, **kwargs)
        end = time.perf_counter()
        print("used time: %s" % str(end - start))
        return m

    return _deco

@timeit
def exchange(lsta, lstb):
    suma, sumb = sum(lsta), sum(lstb)
    d = abs(suma - sumb)
    if d == 0: return d

    bExchange = False
    for indexa, ia in enumerate(lsta):
        if d == 0: break

        for indexb, ib in enumerate(lstb):
            if ia != ib:
                tempd = abs(suma - 2 * ia + 2 * ib - sumb)
                if tempd < d: bExchange, tempindexa, tempindexb, d = True, indexa, indexb, tempd

        if bExchange:
            tt = lstb[tempindexb] - lsta[tempindexa]
            suma, sumb = suma + tt, sumb - tt
            # sumb = sumb - lstb[tempindexb] + lsta[tempindexa]
            lsta[tempindexa], lstb[tempindexb], bExchange = lstb[tempindexb], lsta[tempindexa], False

    return d
#test it
lsta = []
lstb = []
for i in range(1000):
    lsta.append(random.randint(0, 1000000))
    lstb.append(random.randint(0, 1000000))
print(exchange(lsta, lstb))

lsta = []
lstb = []
for i in range(10000):
    lsta.append(random.randint(0, 1000000))
    lstb.append(random.randint(0, 1000000))
print(exchange(lsta, lstb))