题解：P10840 【MX-J2-T1】Turtle and Sequences

yx666 · 2024-08-04 17:52:19 · 题解

P10840 题解

给你一个序列 a_1, a_2, \ldots, a_n。你可以对这个序列进行若干次操作。

设一次操作前序列长度为 m，那么这次操作你可以选择一个整数 i 使得 1 \le i \le m - 1 且 a_i \ne a_{i + 1}，删除 a_{i + 1} 并把 a_i 的值设成任意整数。

求最多能进行多少次操作。

对于所有数据，满足 1 \le n \le 10^5，1 \le a_i \le 10^9。

先说结论。

结论

1. 如果 \forall i\in[1,n-1],a_i=a_{i+1}（即所有 a_i 都相等），答案为 0。

2. 否则，答案为 n-1。

证明

结论 1，证明显然。

对于结论 2，归纳法可证（记 f(i) 表示长度为 i 时，至少存在一对不等的相邻数时，最大操作次数）：

signed main(){
    int n=read(),tp=read();
    for(int i=1;i<n;++i){
        int t=read();
        if(t!=tp){
            printf("%d",n-1);
            return 0;
        }
    }putchar('0');
    return 0;
}