Ilya and a Colorful Walk 解题报告

_Glassy_Sky_ · 2023-08-15 13:02:21 · 题解

题目链接

这道题目一到手，我首先想到的就是两重爆搜。先在输入过程中进行一个特判，判断如果所有的颜色都一样，输出 0 并结束程序。否则用 l 模拟左端点，用 r 模拟右端点，依次搜索每一小段，如果左端点和右端点的颜色不一样，就用 ans 来维护此时的最大值，最后输出答案。

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
int a[MAXN];
int main()
{
    int n, ans = 0, sum = 0;
    cin >> n;
    cin >> a[1]; 
    for(int i = 2; i <= n; i ++)
    {
        cin >> a[i];
        if(a[i] == a[i - 1])//特判统计 
            sum ++;
    }
    if(sum == n - 1)//特判全部一样的情况 
    {
        cout << 0;
        return 0;
    }
    for(int l = 1; l <= n; l ++)//两层爆搜 
        for(int r = l; r <= n; r ++)
            if(a[l] != a[r])
                ans = max(ans, r - l);
    cout << ans;
    return 0;
}

但是这份代码交上去是会 TLE 的，为什么？因为 n 的范围高达 300000，而我们还用了两重循环！于是，现在改进的方法只有将两重循环变成一重循环，并且还要使长度最长。顺着这个思路，我们很容易就想到答案一定包含第一个房子或者最后一个房子，甚至两者都囊括！所以我们就把问题简化成了两个一重循环，一个从头上扫，遇到不一样的，就与之前的最大值比较取最大值。一个从尾巴上扫，原理和之前一样。最后输出两者最大值就好了。下面详见代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
int a[MAXN];
int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, sum = 0, ansl = 0, ansr = 0, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        if(a[i] == a[i - 1])
            sum ++;
    }
    if(sum == n - 1)//还是特判 
    {
        cout << 0;
        return 0;
    }
    for(int l = 1; l <= n; l ++)//从前往后扫 
        if(a[l] != a[n])
            ansl = max(ansl, n - l);
    for(int r = n; r >= 1; r --)//从后往前扫 
        if(a[r] != a[1])
            ansr = max(ansr, r - 1);
    ans = max(ansl, ansr);//两者最大值 
    cout << ans;
    return 0;
}

放一个 AC 凭据吧。