codeforces 616D

题意：给你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;

 }

巴特西

codeforces 616D

最新文章

热门文章