最小增量/递减操作，使长度为k的所有子阵列之和相等

Question

我正在解决一个问题，其中给了我一个长度为N的数组a和一个整数0<K<N。我们需要使长度为K的所有子阵列(包括圆形(的和在最小运算中相等。在一个操作中，我们可以将数组的元素递增或递减1。

我想不出一个算法来做到这一点。对于K=1，我可以计算平均值，然后计算平均值和数组元素之间的绝对差之和。但对于较大的K，有人能给我一个提示吗？

Answer 1

提示：由于循环约束，最终数组应该是第一个K元素的完整重复，如[1,2,3,1,2,3,1,2,3]。因此，如果N不能被K整除，那么所有元素都应该相等，并且它们都应该变为数组的中值。如果N是偶数，则取N/2或N/2+1的最小元素是相同的。否则，需要使a[0], a[K], ...相等，a[1], a[K+1], ...相等，依此类推。通过将每个值更改为相应的中值来独立求解。

Answer 2

我希望以下代码能回答您的问题：

class Solution {
public:
long long int calc(vector<int>& nums) {
long long int n = nums.size();
sort(nums.begin(), nums.end());
if (n % 2 == 0) {
long long int num1 = nums[n / 2];
long long int num2 = nums[(n / 2) - 1];
long long int cnt1 = 0, cnt2 = 0;
for (auto num : nums) {
cnt1 += abs(num - num1);
cnt2 += abs(num - num2);
}
return min(cnt1, cnt2);
} else {
long long int num = nums[n / 2];
long long int cnt = 0;
for (auto num : nums) {
cnt += abs(num - num);
}
return cnt;
}
return 0;
}
long long int makeSubKSumEqual(vector<int>& nums, int k) {
long long int n = nums.size();
if (__gcd(n, (long long)k) != 1) {
long long int ans = 0;
for (int i = 0; i < __gcd(n, (long long)k); i++) {
int j = i;
vector<int> v;
while (j < n) {
v.push_back(nums[j]);
j += __gcd(n, (long long)k);
}
ans += calc(v);
}
return ans;
} else {
return calc(nums);
}
}
};