CF1454C Sequence Transformation 题解

· · 题解

我们先来看题

这道题我们首先就可以想出一个思路：我们枚举从1到 n，遍历一遍这个数组，求出如果保留当前数字的话，需要删除几个区间，再与当前最优解比较并更新最优解，最后把最优解输出即可。

但如果这么做的话，我们不难发现一个问题：时间复杂度是 O(tn^2),而 1 \le t \le 2 \cdot 10^4,\sum_{}n \le 2 \cdot 10^5,很显然是会 TLE 的，所以我们要优化时间复杂度。

我们可以看到，所谓 O(tn^2) 是指三个部分，O(t) 组数据，O(n) 种情况，O(n) 求解。显而易见的，我们只能对 O(n) 求解这一部分进行优化。

为了解决这个问题，我们来复习一下小学奥数——植树问题！

问题：已知街道上有 n 棵树排成一列，每两棵树之间的距离为5米（包括树到街头和树到街尾的距离），问：

（1）假设街两头都栽树，这条路长几米？

（2）假设街两头都不栽树，这条路长几米？

（3）假设街两头只有一头栽树，这条路长几米？

答案：

（1）：5 \times (n-1)

（2）：5 \times (n+1)

（3）：5 \times n

由此我们可以看出，当一段顶头时，就有 n 个区间，当两端顶头时，就有 n-1 个区间，当两端都不顶头时，就有 n+1 个区间。

这道题也是如此，我们求要删几次，就是要求区间数，用上面的方法即可。

所以第一步，我们要离线处理每一个数字存在的次数。

我们这个时候会发现一个问题：

举个例子：1 2 2 3 2 1

我们可以发现，在第一个2和第二个2之间，是没有东西的，理论上来说，它俩之间也要删一次，但它俩之间都没东西了，删什么删？

所以我们在处理之前，还要合并相同且相邻的数字： 这样就正常多了。

第二步就是运用我们上述所说的东西，将求解由 O(n) 简化成 O(1) ，从而把求最优解由 O(n^2) 简化成 O(n)，这样我们就可以愉快地 A 掉这道题了

接下来是你们最开心的代码时刻：

#include<iostream>
#include<cstdio>
using namespace std;
int read(){ //快读 
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int ai[200005]; //未去重的数组 
int a[200005]; //去重的数组 
int tong[200005];
void cf(){
    int n=read();
    int cnt=0;
    for(int i=1;i<=n;i++){ //去重 
        ai[i]=read();
        if(ai[i]!=a[cnt]){
            cnt++;
            a[cnt]=ai[i];
        }
    }
    for(int i=1;i<=cnt;i++) //利用桶排的思想记录“树”的数量 
        tong[a[i]]++;
    int ansi=200004;//将最优解初始化为一个无穷大的数 
    //下面是更新最优解 
    for(int i=2;i<=n-1;i++)
        if(tong[ansi]>tong[a[i]]&&tong[a[i]]!=0) ansi=a[i];
    if(tong[ansi]>=tong[a[1]]&&tong[a[1]]!=0) ansi=a[1];
    if(tong[ansi]>=tong[a[cnt]]&&tong[a[cnt]]!=0) ansi=a[cnt];
    if(a[1]==a[cnt]&&tong[ansi]>=tong[a[1]]-1&&tong[a[1]]!=0) ansi=a[1]; 
    //上面是更新最优解 
    if(cnt==1||cnt==2) printf("%d\n",cnt-1); //特判 
    else{
        if(ai[1]==ansi&&ai[n]==ansi) printf("%d\n",tong[ansi]-1); //当两侧都是最前或最后时，答案是树的数量-1  
        else{
            if(ai[1]==ansi||ai[n]==ansi) printf("%d\n",tong[ansi]);//当两侧有一侧是最前或最后时，答案就是树的数量
            else printf("%d\n",tong[ansi]+1); // 当两侧都不是最前或最后是，答案就是树的数量+1 
        }
    }
    for(int i=1;i<=n;i++){ //初始化 
        ai[i]=0;
        a[i]=0;
        tong[i]=0;
    }
    return;
}
int main(){
    int t=read(); //t组数据 
    tong[200004]=0x3f3f3f; //见32行 
    for(int i=1;i<=t;i++)
        cf();
    return 0;
}

接下来的东西与学术没有关系，大佬可以跳过，直接点赞走人；想摸鱼的可以看完剩下部分，再点赞走人。

传送门