- 反思：
上来方向就错了，仍然是对公式进行化简并找到了规律。诚然，这个方法是效率高，可是花费在代码和调试上的时间已经宣告了这个题目的失败
题目的数据不大，是可以O(n^2)枚举的 - 以后结题的方向：
充分利用枚举！！！上来先考虑枚举，在考虑算法
const int MAXN = 11000;
int ipt[MAXN];
int main()
{
// freopen("in.txt", "r", stdin);
int n, goal;
while (~RII(n, goal))
{
FE(i, 1, n)
RI(ipt[i]);
int Max = -INF, index;
FE(i, 1, n)
{
if (ipt[i] + goal * (1 - i) < 1)
continue;
int t = 0;
FE(j, 1, n)
{
if (ipt[j] - ipt[i] == goal * (j - i))
t++;
}
if (t > Max)
{
Max = t;
index = i;
}
}
cout << n - Max << endl;
int value = ipt[index] - goal * index;
FE(i, 1, n)
{
if (ipt[i] - goal * i > value)
printf("- %d %d\n", i, ipt[i] - goal * i - value);
else if (ipt[i] - goal * i < value)
printf("+ %d %d\n", i, value - ipt[i] + goal *i);
}
}
return 0;
}
接下来完成一下最开始的思路：O(n)
对于位置i和j，如果他们不用进行变化，那么需要满足的条件：ipt[j] - ipt[i] = goal * (j - i)，我们化简一下可以得到：ipt[i] - goal * i =ipt[j] - goal * j，到这里规律就很明显了，可以计算出每个点的ipt[i] - goal * i，计算出这个值相同的数量的最大值。这个地方就有一个坑，题目要求每个点都是正整数而且是递增，那么在ipt[1]是有约束的，必须大于零，判断很简单关键是要想到这个约束。
const int MAXN = 110000;
int ipt[MAXN];
map<int, int> mp;
int main()
{
// freopen("in.txt", "r", stdin);
int t, n, goal;
while (~RII(n, goal))
{
mp.clear();
FE(i, 1, n)
RI(ipt[i]);
FE(i, 1, n)
{
if (ipt[i] - goal * i + goal >= 1)
mp[ipt[i] - goal * i]++;
}
int Max = -INF, value;
FC(it, mp)
{
if ((t = it->second) > Max)
{
Max = t;
value = it->first;
}
}
cout << n - Max << endl;
FE(i, 1, n)
{
if (ipt[i] - goal * i > value)
printf("- %d %d\n", i, ipt[i] - goal * i - value);
else if (ipt[i] - goal * i < value)
printf("+ %d %d\n", i, value - ipt[i] + goal *i);
}
}
return 0;
}