等差数列
给定一个长度为 $n$ 的正整数数列 $a_1,a_2, \ldots, a_n$ 和一个正整数 $k$。
你可以对数列进行以下两种操作：
+ i x ，增加操作，将 $a_i$ 的值增加 $x$（$x \geq 1$）。
- i x ，减少操作，将 $a_i$ 的值减少 $x$（$x \geq 1$）。
要求：在任何时候，你都需要保证每个 $a_i$ 的值都是正整数。
请你使用尽可能少的操作次数，使得数列能够满足：对于所有 $i$（$1 \leq i < n$），$a_{i+1}−a_i=k$ 均成立。
请你输出所需要的最少操作次数以及对应的具体操作方案。
输入格式
第一行包含两个整数 $n,k$。
第二行包含 $n$ 个整数 $a_1,a_2, \ldots ,a_n$。
输出格式
第一行输出一个整数 $p$，表示所需要的最少操作次数。
接下来 $p$ 行，用来输出具体操作方案，每行输出一个具体操作 + i x 或 - i x。你需要保证输出的 $i$ 和 $x$ 均为正整数，且 $1 \leq i \leq n$。
如果最少操作次数的方案不唯一，则输出任意一种方案均可。
数据范围
前 $3$ 个测试点满足 $1 \leq n \leq 7$。
所有测试点满足 $1 \leq n \leq 1000$，$1 \leq k \leq 1000$，$1 \leq a_i \leq 1000$。
输入样例1：
4 1 1 2 1 5
输出样例1：
2 + 3 2 - 4 1
输入样例2：
4 1 1 2 3 4
输出样例2：
0
输入样例3：
7 1 1 1 2 3 4 5 6
输出样例3：
6 + 2 1 + 3 1 + 4 1 + 5 1 + 6 1 + 7 1
解题思路
先给出我的做法，当时做的时候没写出来，今天回来补题又写出来了。
首先我们不考虑改变$a_1$，可以发现就是要把序列变成一个以$a_1$为首项，公差为$k$的等差数列，而现在$a_1$固定，意味着其余项$a_i$都是一个固定的值，因此如果原序列的$a_i \ne a_1 + (i - 1) \cdot k$，那么就要改变一次，因此最小改变次数就是与对应项不同的个数。
因此如果$a_1$固定不变，那么答案也就固定不变，因此为了得到最小的改变次数，我们就需要改变$a_1$。那么$a_1$要改成什么数呢？对于原序列，我们先算出每一项所在公差为$k$的等差数列的首项，即算出每一项的$a_1^\prime = a_i - (i - 1) \cdot k$，然后开个哈希表统计$a_1^\prime$的次数，假设最后统计出出现次数最多的数值$x$，那么就把$a_1$变成$x$。这是因为如果把$a_1$变成$x$那么对于算出$a_1^\prime = x$的项就不需要进行改变（因为$a_i = x + (i - 1) \cdot k$），选择出现次数最多的$x$意味着需要改变的项越小，这是典型的贪心思想。
需要注意的是，我们只统计正整数的$a_1^\prime$，因为题目要求每个数都是正整数，如果某项算出的$a_1^\prime$不是正整数，而$a_1$只能是正整数，因此该项无论$a_1$取什么都要改一次。
AC代码如下，时间复杂度为$O(n)$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 1010;
5
6 int a[N];
7 struct Node {
8 char c;
9 int x, val;
10 };
11
12 int main() {
13 int n, m;
14 scanf("%d %d", &n, &m);
15 for (int i = 1; i <= n; i++) {
16 scanf("%d", a + i);
17 }
18 unordered_map<int, int> cnt;
19 cnt[a[1]]++; // 一开始a[1]本身出现一次
20 for (int i = 2; i <= n; i++) {
21 int t = a[i] - (i - 1) * m;
22 if (t > 0) cnt[t]++; // 只有正整数才统计
23 }
24 int x = a[1], maxv = 1; // 一开始默认不改变a[1]
25 for (auto &it : cnt) {
26 if (it.second > maxv) maxv = it.second, x = it.first; // 找到出现次数最多的数
27 }
28 vector<Node> ans;
29 for (int i = 1; i <= n; i++) {
30 int t = a[i] - (x + (i - 1) * m); // a[i]与x + (i - 1)*k的插值，如果等于0表示不需要改变
31 if (t > 0) ans.push_back({'-', i, t});
32 else if (t < 0) ans.push_back({'+', i, -t});
33 }
34 printf("%d\n", ans.size());
35 for (auto &it : ans) {
36 printf("%c %d %d\n", it.c, it.x, it.val);
37 }
38
39 return 0;
40 }
再给出y总的做法。
首先容易发现答案最大为$n$，因为每个数最多改变$1$次，实际上还可以让$a_1$固定，改变剩余的$n-1$个数，因此答案最大值就变成了$n-1$。因此现在最多改变$n-1$次，意味着至少有一项是不会改变的，因此我们可以枚举每一项，固定该项$a_i$，然后再枚举一遍序列进行比较，如果$a_j \ne a_i + (j - i) \cdot k$，那么$a_j$就需要改变。通过枚举所有项就可以找到最小改变次数了。
AC代码如下，时间复杂度为$O(n^2)$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 1010;
5
6 int a[N];
7 struct Node {
8 char c;
9 int x, val;
10 };
11
12 int main() {
13 int n, m;
14 scanf("%d %d", &n, &m);
15 for (int i = 1; i <= n; i++) {
16 scanf("%d", a + i);
17 }
18 vector<Node> ans;
19 for (int i = 1; i <= n; i++) {
20 vector<Node> vec;
21 for (int j = 1; j <= n; j++) {
22 int t = a[i] + (j - i) * m;
23 if (t <= 0) { // 每个数都要是正整数
24 vec.clear();
25 break;
26 }
27 if (a[j] > t) vec.push_back({'-', j, a[j] - t});
28 else if (a[j] < t) vec.push_back({'+', j, t - a[j]});
29 }
30 if (!vec.empty() && (ans.empty() || ans.size() > vec.size())) ans = vec;
31 }
32 printf("%d\n", ans.size());
33 for (auto &it : ans) {
34 printf("%c %d %d\n", it.c, it.x, it.val);
35 }
36
37 return 0;
38 }
参考资料
AcWing 4780. 等差数列（AcWing杯 - 周赛）：https://www.acwing.com/video/4557/
标签：正整数,改变,次数,int,leq,ans,等差数列 From： https://www.cnblogs.com/onlyblues/p/17050962.html