zoj 3790

1453 ワード

スキャンします.
const  int  maxn = 100008 ;
int    x[maxn]  , c[maxn] ;
int    n , k ;
vector <int> g[maxn] ;

int main(){
    int i  , m  , t  , d  , L , R , a ;
    while(cin>>n>>k){
         for(i = 0 ; i < n ; i++){
            scanf("%d" , &c[i]) ;
            x[i] = c[i]  ;
         }
         sort(x , x+n) ;
         m = unique(x , x+n) - x ;
         for(i = 0 ; i < n ; i++)
            c[i] = upper_bound(x , x+m , c[i]) - x ;
         for(i = 1 ; i <= m ; i++) g[i].clear() ;
         for(i = 0 ; i < n ; i++)
             g[c[i]].push_back(i) ;
         int s = 1  ;
         for(a = 1 ; a <= m ; a++){
            t = 1 ;
            d = k ;
            L = 0 ;
            for(R = 1  ; R < g[a].size()  ; R++){
                if(g[a][R] - g[a][R-1] == 1){
                     t++ ;
                     s = max(s , t) ;
                     continue ;
                }
                d -= g[a][R] - g[a][R-1] - 1 ;
                if(d >= 0){
                     t++ ;
                     s = max(s , t) ;
                }
                else{
                    while(d < 0){
                         L++ ;
                         d += g[a][L] - g[a][L-1] - 1 ;
                         t-- ;
                    }
                    t++ ;
                }
            }
         }
         cout<< s <<endl ;
    }
    return 0;
}