题解 Turtle and Sequences

思路

可以用一个测试用例来找规律。 比如说有这几个数:
1 1 4 5 1 4
可以发现，只要遇到两个不同的数 $x$ 和 $y$， 可以保证操作结束后得到的新数跟所有的数不一样。 所以又可以跟其他的数进行操作了。

所以只有这两个情况了：

• 有一对不相同：总共 $n - 1$ 次。
• 都相同：总共执行了 $0$ 次。

解题方法

只要遇到两个数不同，输出 $n - 1$，否则输出 $0$。
复杂度为$O(n)$。

Code

#include <bits/stdc++.h>
using namespace std;

int a[100005];

int main(){
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int cnt = 0;
    for (int i = n; i > 1; i--) {
        if(a[i] != a[i - 1]) {
            cnt = n - 1;
            break;
        }
    }

    cout << cnt << "\n";
    
    return 0;
}