题目描述：
给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。
你可以执行下述运算任意次：
- 选中
arr 中任意一个元素，并使其值加上 1 或减去 1 。
执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。
子数组 是数组的一个连续部分。
数据范围：
$1\le k \le arr.len \le 10^5, 1\le arr[i] \le 10^9$
题解：
可以发现除以 $k$ 余数相同的位置需要修改成一样的，就是一个分组中位数贪心。但是分组时有点不同，比如 [10,9,1,10,5], k = 3。余数为 $0$ 的组为 0,3,1,4,2,(0)，把所有的数字都分到了这一组。 $1$ 又可以作为余数为 $1$ 的组，又可以作为余数为 $0$ 的组。可以使用一个 $set$ 标记一下余数为 $p$ 的组是否已经遍历过了，然后求该分组时，一直遍历直到出现了重复元素，在遍历这一组时可能也已经把别的组遍历过了。遍历后面的组时，首先检查是否已经在 $set$ 内。
也可以使用裴蜀定理，一个数组有两个循环节，一个是 $n$ ，一个是 $k$ 。那么 $\gcd(n,k)$ 一定是循环节，而且是最小的循环节。可以只遍历这个循环节分组的。
证明：假设从起点出发，先走了 $x$ 个 $n$ ，又走了 $y$ 个 $k$ ，即 $x\times n + y \times k = z$ ，其中根据裴蜀定理 $z$ 一定是 $p \times \gcd(n, k)$ 。所以走 $p$ 个 $\gcd(n,k)$ 也能到达该位置。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
long long makeSubKSumEqual(vector<int> &arr, int k)
{
int n = arr.size();
k = __gcd(n, k);
long long ans = 0;
for (int i = 0; i < k; ++i)
{
vector<int> nums;
for (int j = i; j < 2 * n - 1; j += k)
{
nums.emplace_back(j % n);
}
sort(nums.begin(), nums.end(), [&](const int &x, const int &y)
{ return arr[x] < arr[y]; });
int aim = arr[nums[(nums.size()) / 2]];
long long cnt= 0;
for (auto &x : nums)
{
cnt += abs(aim - arr[x]);
arr[x] = aim;
}
ans += cnt;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
long long makeSubKSumEqual(vector<int> &arr, int k)
{
int n = arr.size();
long long ans = 0;
unordered_set<int> mp;
for (int i = 0; i < k; ++i)
{
if(mp.count(i)) continue;
vector<int> nums;
nums.emplace_back(i);
for (int j = (i + k) % n; j != i ; j = (j + k) % n)
{
nums.emplace_back(j);
mp.insert(j);
}
sort(nums.begin(), nums.end(), [&](const int &x, const int &y)
{ return arr[x] < arr[y]; });
int aim = arr[nums[(nums.size()) / 2]];
long long cnt= 0;
for (auto &x : nums)
{
cnt += abs(aim - arr[x]);
arr[x] = aim;
}
ans += cnt;
}
return ans;
}
};
|