使数组对和相等的最小操作数

Question

给你一个整数列表，长度为偶数。考虑这样一个操作，您在nums中选择任意数字，并用[1,max（nums）]之间的值更新它。返回所需的操作数，使得对于每个i，nums[i]+nums[n-1-i]等于相同的数。问题可以贪婪地解决。

注意：n是数组的大小，max（nums）是nums中的最大元素。

null

设i=0,nums[0]+nums[6-1-0]=4。

i=1,nums[1]+nums[6-1-1]=14。

i=2,nums[2]+nums[6-1-2]=9。

int operations = 0;
for(int i=0; i<nums.size()/2; i++) {
    if(nums[i] + nums[nums.size()-1-i] == mid)
        continue;
        
    if(nums[i] + nums[nums.size()-1-i] > mid) {
        if(nums[i] + 1 <= mid || 1 + nums[nums.size()-1-i] <= mid) {
            operations++;
        } else {
            operations += 2;
        }
    } else if (maxnums + nums[nums.size()-1-i] >= mid || nums[i] + maxnums >= mid) {
        operations++;
    } else {
        operations += 2;
    }
}

选择中位数不是最优的方法吗？有人能提供一个更好的方法吗？

Answer 1

为了提供一些理论--我们可以很容易地说明所需更改的上限是n/2，其中n是元素的数量。这是因为可以对1+C和max(nums)+C之间的任何内容进行一次更改，其中C是一对中的两个元素之一。对于最小的C，我们最高可以绑定max(nums)+1；对于最大的C，我们可以将1+max(nums)绑定到最低。

由于这两个边界在最坏的情况下是相等的，我们可以保证有一个最多n/2更改的解决方案，使至少一个C（数组元素）保持不变。

由此我们得出结论，一个最优解要么（1）至少有一对，其中两个元素都不改变，其余的元素每对只需要改变一次，要么（2）我们的最优解有n/2改变，如上所述。

因此，我们可以继续测试每个现有对的单一或零变化可能性作为候选。我们可以迭代每对两到三种可能性的排序列表，并用每个成本和索引标记。（本页上的其他作者也提供了类似的方法和代码。）