CF1119A题解

· · 题解

思路

这个题的重点是答案一定包括点 1 或 n，证明如下。

考虑使用反证法。假设有 i，j 两点距离最远且颜色不同 （ 1 < i < j < n），那么如果 i 的颜色与 n 不同，i 与 n 比原来更优，矛盾。如果 j 与 1 的颜色不同，1 与 j 比原来更优，矛盾。因此 i 的颜色与 n 相同，j 与 1 的颜色相同。由于 i 与 j 的颜色不同，那么 1 与 n 的颜色也不同，比原来更优，矛盾。因此答案一定包括 1 或 n。

做法

只需从前往后，从后往前扫两次，答案取最大值即可。

代码如下。

#include<bits/stdc++.h>
using namespace std;
int n,a[300005],first,last,ans1,ans2;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    first=1,last=n;
    while(1){
        if(a[first]!=a[last]){
            ans1=last-first;
            break;
        }else first++;
    }
    first=1,last=n;
    while(1){
        if(a[first]!=a[last]){
            ans2=last-first;
            break;
        }else last--;
    }
    cout<<max(ans1,ans2);
    return 0;
}