[USACO13JAN]牛的阵容Cow Lineup

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题目

luogu3069

思路

一道被恶意评分的题目（最多只有绿啊，怎么就蓝了？）。
这题用离散化，尺取法。枚举r就好了。
为什么？？
先看看这题。
再回来看本题，有没有什么想法？
在一个区间中，一共有<=k+1种数，是不是就可以保证这些数都可以删除，只留下一种数字。那我们是不是只要枚举每一个位置，找到符合的区间，就可以记录（更新）答案了呢？（如果我说不清楚请谅解，可以看代码理解）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int n,a[maxn],k,b[maxn],c[maxn];
//a,b数组用于离散化,c数组表示当前这种颜色有几个
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];
    sort(b+1,b+1+n); int len=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
    //前面为离散化，复杂度为o(nlogn)
    int l=1,r=0,now=0,ans=0;
    //l,r不解释,now为当前区间有几种颜色
    while(r<=n){
        r++;//等同于for(int r=1;r<=n;r++)
        if(!c[a[r]])now++; c[a[r]]++;//当前的颜色没有出现过，now++。
        while(l<=n&&now>k+1){//直到找到符合的区间
            c[a[l]]--; if(!c[a[l]])now--;
            l++;//l不用回到之前，为什么呢？
            //因为尺取法是在有单调性的前提才用的。
            //什么单调性呢？自己想去
        }
        ans=max(ans,c[a[r]]);//记录/更新答案
    }
    printf("%d\n",ans);
    return 0;
}

就这样，又水了一题，谢谢！！