original: link

Problem: 2449. 使数组相似的最少操作次数

解题方法

1.分组，使得nums,target形如$(a_0,a_1,\cdots,a_i,b_0,b_1,\cdots,c_j)$，其中 $a_0,a_1,\cdots, a_i$ 为奇数，$b_0, b_1,\cdots, b_j$为偶数，在nums上的操作不能改变元素奇偶性，所以输入nums,target中奇偶元素个数$i,j$必相等，因此分组后nums,target奇数、偶数分前后两段对应

2.使得数组相似需要两步：A).nums中奇数和与偶数和调整与target一致 B).nums中奇数$a_0, a_1, \cdots, a_i$与target中奇数依次对齐，偶数同理。

3.因此计算odd_above, odd_below, even_above, even_below为nums逐位置与target比较，奇数（偶数）超出（少于）部分的累加和，由于输入保证合法，必有abs(even_below - even_above) == abs(odd_below - odd_above),这是一个与操作方案无关的定值，也就是条件A之成本

4.随后nums中奇数$a_0, a_1, \cdots, a_i$与target中奇数依次对齐成本为min(odd_below, odd_above),同理偶数依次对齐成本为min(even_above, even_below)

5.所以仅剩问题就是如何决定操作方案对应的num和target的对齐顺序，也就是最小化min(odd_below, odd_above)，用反证法可证明两个数组偶数、奇数分别降序排列时，条件B的成本最小。以奇数为例，假设nums中两个数为$a < b$，target中两个数为$c < d$，易证以$(a,d), (b,c)$比较时（按$[a, b], [c,d]$有无交集分两种情况讨论）min(odd_below, odd_above)增加或不变，所以先贪心地降序或升序排列两个数组

6.ans = (abs(odd_below - odd_above) + min(odd_below, odd_above) + min(even_above, even_below)) / 2;

复杂度

• 时间复杂度:

$O(nlog(n))$

• 空间复杂度:

$O(1)$

Code

class Solution {
public:
  long long makeSimilar(vector<int> &nums, vector<int> &target) {
    auto f = [](const int a, const int b) {
      if ((a & 1) ^ (b & 1))
        return bool(a & 1);
      return a > b;
    };
    sort(nums.begin(), nums.end(), f);
    sort(target.begin(), target.end(), f);
    const auto n = nums.size();
    long long odd_above = 0, odd_below = 0, even_above = 0, even_below = 0;
    for (int i = 0; i < n; ++i) {
      int dif = abs(nums[i] - target[i]);
      if (nums[i] & 1)
        (nums[i] > target[i] ? odd_above : odd_below) += dif;
      else
        (nums[i] > target[i] ? even_above : even_below) += dif;
    }
    long long ans = 0;
    ans += abs(odd_below - odd_above) + min(odd_below, odd_above) + min(even_above, even_below);
    return ans >> 1;
  }
};