Turtle and Sequences题解

思路

先说一个错误的思路

我一开始做的思路有点问题，把这道题当成了类似去重的题。 就是在输入的时候，如果输入的数与上一个数不同，就读入，否则跳过。最后数组内数的多少就是答案。 写完调试了老半天，好不容易把样例调试对了，交上去喜提53分。

后来重新读了题，才发现貌似理解错了题目的意思。举一个例子。

以下面样例为例：

7
1 3 3 3 3 2 1

如果按照原来的思路，就会得到 $3$ 的结果。但实际上，答案应该是 $6$。具体过程如下。 由于可以将值设成任意整数，那我们设 $k$ 为一个很大的整数。

步骤见下：

操作次数    数组
1           1 3 3 3 3 k
2           1 3 3 3 k+1
3           1 3 3 k+2
4           1 3 k+3
5           1 k+4
6           k+5

当然步骤不是唯一的。

由此可见，只要保证操作结束后得到的数与前面不同，就可以继续进行操作。操作了 $n - 1$ 次。

特殊情况

当所有数都一样时，答案为 $0$，易证。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,flag,a[100005];
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>a[1];
	for(int i=2;i<=n;i++)
	{
		cin>>a[i];
		if(a[i-1]!=a[i]) flag=1;
	}
	if(flag) cout<<n-1;
	else cout<<0;
	return 0;
}

写篇题解不容易，求点赞。不足请指出。