题目链接：http://codeforces.com/problemset/problem/402/B
题目意思：给出n个数和公差k，问如何调整使得ai + 1 - ai = k。（1 ≤ i < n），即等差数列，求出最少的调整次数。（调整的操作包括向一个数添加或者减少某个数，使得后一个数-前一个数 = 公差）。
方法一：
对于每一个数ai，求出以ai为基准，在ai之前和在ai之后不满足等差数列的个数。直到扫描整个序列结束，选出个数最少的，，即调整的次数最少，然后再一次扫描整个序列，算出每一个数需要调整的大小即可。要注意的是，每一个需要调整的数调整之后都需要满足>= 1！！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 using namespace std; 5 6 const int maxn = 1000 + 10; 7 int a[maxn], rea[maxn][2]; // a:原始输入序列 rea:保存需要调整的数的调整大小 8 char ch[maxn]; 9 10 int main() 11 { 12 int d, n, i, j; 13 while (scanf("%d%d", &n, &d) != EOF) 14 { 15 for (i = 1; i <= n; i++) 16 scanf("%d", &a[i]); 17 int ans = maxn, cnt = 0; 18 int flag, rec = 1; 19 for (i = 1; i <= n; i++) 20 { 21 flag = 0; 22 for (j = i-1; j >= 1; j--) // 扫描以ai为基准的前面的数 23 { 24 if (a[i] - (i-j)*d != a[j]) 25 { 26 if (a[i] - (i-j)*d >= 1) 27 cnt++; 28 else // 调整后的数不满足 >= 1 29 { 30 flag = 1; 31 break; 32 } 33 } 34 } 35 for (j = i+1; j <= n && !flag; j++) // 扫描以ai为基准的后面的数 36 { 37 if (a[i] + (j-i)*d != a[j]) 38 { 39 if (a[i] + (j-i)*d >= 1) 40 cnt++; 41 else 42 { 43 flag = 1; 44 break; 45 } 46 } 47 } 48 if (cnt < ans && !flag) // ans保存最少的调整次数 49 { 50 ans = cnt; 51 rec = i; // 记录当前得出最少调整数量的以第i个数为基准的下标 52 } 53 cnt = 0; 54 } 55 int l = 0; 56 cnt = 0; 57 for (j = rec-1; j >= 1; j--) // 前面开始调整 58 { 59 if (a[rec] - (rec-j)*d != a[j]) 60 { 61 cnt++; 62 if (a[rec] - (rec-j)*d > a[j]) 63 { 64 ch[l] = '+'; 65 rea[l][0] = j; 66 rea[l][1] = a[rec] - (rec-j)*d - a[j]; 67 } 68 else 69 { 70 ch[l] = '-'; 71 rea[l][0] = j; 72 rea[l][1] = a[j] - (a[rec] - (rec-j)*d); 73 } 74 l++; 75 } 76 } 77 for (j = rec+1; j <= n; j++) // 后面开始调整 78 { 79 if (a[rec] + (j-rec)*d != a[j]) 80 { 81 cnt++; 82 if (a[rec] + (j-rec)*d > a[j]) 83 { 84 ch[l] = '+'; 85 rea[l][0] = j; 86 rea[l][1] = a[rec] + (j-rec)*d - a[j]; 87 } 88 else 89 { 90 ch[l] = '-'; 91 rea[l][0] = j; 92 rea[l][1] = a[j] - (a[rec] + (j-rec)*d); 93 } 94 l++; 95 } 96 } 97 printf("%d ", l); 98 for (i = 0; i < l; i++) 99 printf("%c %d %d ", ch[i], rea[i][0], rea[i][1]); 100 } 101 }
方法二：
考虑到原始序列中每个数的范围是[1, 1000]。因此可以对a[1] 从 [1, 1000] 里依次取数，再根据公差算出对应的a[2]～a[n]的值，与输入序列的a[2] ～ a[n] 比较，累加不同的数cnt。直到a[1] 完全取尽[1, 1000]范围内的数。当然a[1]每取一个数，都有对应的cnt，求出最少的cnt还有对应的a[1]的值。最后根据最少cnt和a[1]，对初始序列不符合项进行更改。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 using namespace std; 5 6 const int maxn = 1000 + 10; 7 int a[maxn]; 8 9 int main() 10 { 11 int n, k, i, j; 12 while (scanf("%d%d", &n, &k) != EOF) 13 { 14 for (i = 1; i <= n; i++) 15 scanf("%d", &a[i]); 16 int p, tmp, cnt, mini; 17 mini = maxn; 18 for (i = 1; i <= 1000; i++) 19 { 20 tmp = i, cnt = 0; 21 for (j = 1; j <= n; j++) 22 { 23 if (a[j] != tmp) 24 cnt++; 25 tmp += k; 26 } 27 if (cnt <= mini) 28 { 29 mini = cnt; 30 p = i; 31 } 32 } 33 printf("%d ", mini); 34 for (i = 1; i <= n; i++) 35 { 36 if (p != a[i]) 37 { 38 if (p > a[i]) 39 printf("+ %d %d ", i, p-a[i]); 40 else 41 printf("- %d %d ", i, a[i]-p); 42 } 43 p += k; 44 } 45 } 46 return 0; 47 }