gpt4 book ai didi

arrays - 需要多少次交换才能使数组 a 和 b 之和的差最小?

转载 作者:行者123 更新时间:2023-12-04 12:32:54 24 4
gpt4 key购买 nike

给定 2 个整数数组 a[]b[]n (1 <= n <= 100) 大小相同编号自 1 to n .
(0 <= a[i], b[i] <= 6)
您可以交换任何 a[i]b[i] .
需要多少次交换才能使数组 a[] 的总和之差|和 b[]是最低的?
然后打印出来:

  • 掉期次数
  • 交换索引
  • 两个数组和的差

  • 示例
    n = 6

    a[] = { 1, 1, 4, 4, 0, 6 }

    b[] = { 6, 3, 1, 1, 6, 1 }
    结果
     - 2 (The number of swaps)
    - 5, 6 (The swapped indexes)
    - 0 (The difference of sums of the arrays)
    说明
    如果交换 a[5] b[5] a[6] b[6] 这需要 2 交换、数组 a[]b[]会变成:
    a[] = {1, 1, 4, 4, 6, 1}

    b[] = {6, 3, 1, 1, 0, 6}
    a[]的总和是 1 + 1 + 4 + 4 + 6 + 1 = 17 b[]的总和是 6 + 3 + 1 + 1 + 0 + 6 = 17所以两个和的差是 0 .

    最佳答案

    这是一个迭代方法,可以保存到目前为止的差异并更新交换以实现它们所需的最小索引列表。
    JavaScript 代码:

    function update(obj, d, arr){
    if (!obj[d] || obj[d].length > arr.length)
    obj[d] = arr;
    }

    function f(A, B){
    let diffs = {0: []};

    for (let i=0; i<A.length; i++){
    const newDiffs = {};

    for (d in diffs){
    // Swap
    let d1 = Number(d) + B[i] - A[i];
    if (diffs.hasOwnProperty(d1) && diffs[d1].length < diffs[d].length + 1)
    update(newDiffs, d1, diffs[d1]);
    else
    update(newDiffs, d1, diffs[d].concat(i+1));

    d1 = Number(d) + A[i] - B[i];
    if (diffs.hasOwnProperty(d1) && diffs[d1].length < diffs[d].length)
    update(newDiffs, d1, diffs[d1]);
    else
    update(newDiffs, d1, diffs[d]);
    }

    diffs = newDiffs;
    }

    console.log(JSON.stringify(diffs) + '\n\n');

    let best = Infinity;
    let idxs;

    for (let d in diffs){
    const _d = Math.abs(Number(d));
    if (_d < best){
    best = _d;
    idxs = diffs[d];
    }
    }

    return [best, idxs];
    };

    var A = [1, 1, 4, 4, 0, 6];
    var B = [6, 3, 1, 1, 6, 1];

    console.log(JSON.stringify(f(A, B)));

    关于arrays - 需要多少次交换才能使数组 a 和 b 之和的差最小?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64069111/

    24 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com