秀姿势

jzoj 3464

题目大意

有n个数，每个数都有一个分组，现在问你最多去掉k个分组后，做多有多少个数是连续的同组的

输入样例

9 1 2 7 3 7 7 3 7 5 7

输出样例

4

样例解释

总共有9个学生，最多只能刷一次学生。
若不刷，最长完美学生连续子序列长度为2
若刷掉考第3门考得好的学生，则学生序列变成2 7 7 7 7 5 7，最长完美学生连续子序列长度为4.

数据范围

对于10%的数据：$n⩽10$
对于30%的数据：$n⩽1000$
对于100%的数据：$1⩽n⩽100000$

解题思路

题目就是找一个连续的子串里面包含的组数不超过k+1，这样删去k个后还剩一个，然后找这些子串中出现的最多的数出现的次数
我们从一开始让数字进队，当组数大于k+1时就从队尾出，直到符合为止

代码

#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int n, m, s, x, ans, a[100010]; map < int , int > p; int main() {scanf("%d%d", &n, &m);m += 1;x = 1;for (int i = 1; i <= n; ++i){scanf("%d", &a[i]);if (!p[a[i]]) s++;//新的组p[a[i]]++;while (s > m){p[a[x]]--;if (!p[a[x]]) s--;//这个组没了x++;}ans = max(ans, p[a[i]]);//求最大值}printf("%d", ans);return 0; }

总结

以上是生活随笔为你收集整理的秀姿势（jzoj 3464）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。