题意:给你n个数,找出一个最大的区间,满足:不同的数值个数不超过k;
//我开始又看错题了、 以为是找出一个最大区间,里面的数的最大值不超过k;
思路:利用一个窗口滑动,左端点表示当前位置,右端点表示目前这段数列符合要求, 每增加一个长度,判断是否合理,不然平移左端点。 思路来自:http://blog.csdn.net/u011528035/article/details/50521870#;
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int qq=1e6;
int num[qq];
int dp[qq];
int l,r,k,n,ans,dif,p,q; //定义的全局变量自动初始化为0(包括数组).
int main()
{
cin >> n >> k;
l=r=;
for(int i=;i<=n;++i){
cin >> num[i];
if(!dp[num[i]]) ++dif;
dp[num[i]]++;
r=i;
if(dif>k){
for(int j=l;j<=r;++j){
dp[num[j]]--;
if(!dp[num[j]]){
dif--;l=j+;break;
}
}
}
if(r-l+>ans){
ans=r-l+;q=l;p=r;
}
}
cout << q << " " << p << endl;
}