自动搬运

查看原文

来自洛谷，原作者为

	NTG_Adiord **

搬运于2025-08-24 21:44:58，当前版本为作者最后更新于2018-08-23 21:41:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题为啥是蓝的啊

离散化，然后再。。。。。算了代码解释

#include <bits/stdc++.h>
using namespace std;
int n;
map<int,int> mp;
//离散化
int a[100001];
//存离散化后的数组
int hav[100001];
//存当前区间内，对应数字出现过的次数
int mxl;
//反正就是计数一下
int typ,k;//当前区间里有多少种
int ans;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(!mp[a[i]])mp[a[i]]=++mxl;
        //如果当前数字没有出现过，就给他分配一个新的离散化值
		a[i]=mp[a[i]];
	}
	int l=1,r=0;
    //区间
	while(r<=n){
		r++;
        //右移
		if(hav[a[r]]==0)typ++;//如果这个数字第一次出现，种类++
		hav[a[r]]++;
		while(typ==k+2){
        //删除k种，说白了允许当前区间内有k+1种
        如果是k+2种就得删除了
			hav[a[l]]--;
        //左界右移，减少左界位置上值得数量
			if(hav[a[l]]==0)typ--;
        //没了就种类--
			l++;
		}
		ans=max(ans,hav[a[r]]);
        //统计答案
	}
	printf("%d",ans);
    //输出
}

一开始看这道题，蓝的，打算先放放

看了好几篇题解，set,balabala,什么玩意....

按照多篇题解的想法打了一下，也就这样