秀姿势【模拟】【哈希】

姿势【模拟】【哈希】"/>

秀姿势【模拟】【哈希】

题目大意：

一个序列，去掉 k k $k$个数字，使最长的完美连续子序列尽量长。

思路：

队列+哈希/map/" role="presentation">/map//map/$/map/$快拍+二分

用队列维护一个区间，使得这个区间的不同数字个数不超过 k+1 k + 1 $k+1$，统计出来的每个合法区间的众数的数量的最大值便为答案。

---

代码：

#include <cstdio>
#include <iostream>
#include <queue>
#include <map>
using namespace std;int n,k,x,s,a,ans;
queue<int> q;
map<int,int> num;  //每个数字的个数int main()
{scanf("%d%d",&n,&k);for (int i=1;i<=n;i++){scanf("%d",&x);if (!num[x])  //队列里没有这个数字{s++;while (s>k+1)  //数字个数超过可k{a=q.front();  q.pop();num[a]--;  //这个数字数量减一if (!num[a]) s--;  //没有这个数字了}}num[x]++;  q.push(x);if (num[x]>ans) ans=num[x];  //求最大值}printf("%d\n",ans);return 0;
}