等差数列
给定一个长度为 $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/
原文链接: https://www.cnblogs.com/onlyblues/p/17050962.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/311866
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
