奇数偶数分类讨论贪心
作者:
远方传来风笛
,
2022-10-24 18:26:59
,
所有人可见
,
阅读 123
6217. 使数组相似的最少操作次数
给你两个正整数数组 nums 和 target ,两个数组长度相等。
在一次操作中,你可以选择两个 不同 的下标 i 和 j ,其中 0 <= i, j < nums.length ######,并且:
令 nums[i] = nums[i] + 2 且
令 nums[j] = nums[j] - 2 。
如果两个数组中每个元素出现的频率相等,我们称两个数组是 相似 的。
请你返回将 nums 变得与 target 相似的最少操作次数。测试数据保证 nums 一定能变得与 ######target 相似。
示例 1:
输入:nums = [8,12,6], target = [2,14,10]
输出:2
解释:可以用两步操作将 nums 变得与 target 相似:
- 选择 i = 0 和 j = 2 ,nums = [10,12,4] 。
- 选择 i = 1 和 j = 2 ,nums = [10,14,2] 。
2 次操作是最少需要的操作次数。
class Solution {
public:
long long makeSimilar(vector<int>& nums, vector<int>& target) {
int n = nums.size();
vector<int> a(n), b(n), c(n), d(n);
for(auto x : nums){
if(x % 2 == 0) a.push_back(x);
else b.push_back(x);
}
for(auto x : target){
if(x % 2 == 0) c.push_back(x);
else d.push_back(x);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
sort(c.begin(), c.end());
sort(d.begin(), d.end());
long long ans = 0;
for(int i = 0; i < a.size(); i ++) ans += abs(a[i] - c[i]) / 2;
for(int i = 0; i < b.size(); i ++) ans += abs(b[i] - d[i]) / 2;
return ans / 2;
}
};