hdu 6602 Longest Subarray 尺取法

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6602

题目大意为：找一个最大区间，其中区间出现的数的次数大于等于k。

所有我们只需要记录一下每个数出现的次数，在所有的数组中出现小于k次的肯定不在区间内。然后分别枚举区间左右端点，以出现的次数作为优化。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005],num[100005];
int p[100005];
int main(){
int n,c,k;
map<int,int>mp;
int ans;
while(scanf("%d%d%d",&n,&c,&k)>0){
ans=0;
mp.clear();
for(int i=1;i<=n;i++){
scanf("%d",a+i);
num[a[i]]++;
}
int l=1,r=1;
//扩展区间左边
while(l<=n){
//扩展区间右边
while(r<=n&&num[a[r]]>=k){
if(mp[p[a[r]]]>0)
mp[p[a[r]]]--;
if(mp[p[a[r]]]==0)
mp.erase(p[a[r]]);
p[a[r]]++;
mp[p[a[r]]]++;
r++;
}
while(l<r){
if(mp.begin()->first >= k ){
ans = max(ans,r-l);
}
if(mp[p[a[l]]]>0)
mp[p[a[l]]]--;
if(mp[p[a[l]]]==0){
mp.erase(p[a[l]]);
}
p[a[l]]--;
if(p[a[l]]!=0)
mp[p[a[l]]]++;
num[a[l]]--;
l++;
}
l=r+1;
r++;
}
cout << ans <<endl;
}
} 

最后

以上就是顺心冰棍为你收集整理的hdu 6602 Longest Subarray 尺取法的全部内容，希望文章能够帮你解决hdu 6602 Longest Subarray 尺取法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。