ZOJ 3790 Consecutive Blocks

大致题意就是给你一个数列，让你最多移除K个数字，使得连续的相同数字的长度最大，并求出最大长度。

我们将此序列按颜色排序，颜色相同的话按位置排序，那么排完序之后颜色相同的blocks就在一起，只是他们的位置不同而已。因此颜色相同的两个相邻blocks的位置之差-1就是要移除的个数。

当发现所剩的移除个数不足时，那么就删除左边已经连续放在一起的block，同时把那部分所消耗的移除个数加回来;如果所剩移除个数充足那么长度就+1。如果发现相邻的两个block颜色不同那么就要重新开始，所剩移除个数就要重新赋值为初值K，左边的位置变为i，长度变为1,重新计算。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; 
const int MAXN = 200010; 
struct Node{
    int color, pos; 
    bool operator < (const Node& A) const{
        if(color == A.color) return pos < A.pos; 
        return color < A.color; 
    } 
}; 
Node block[MAXN]; 
int main(){
    int n, k; 
#ifndef ONLINE_JUDGE
    freopen("in.cpp", "r", stdin); 
#endif
    while(~scanf("%d%d", &n, &k)){
        for(int i = 1; i <= n; i ++){
            scanf("%d", &block[i].color); 
            block[i].pos = i; 
        }
        sort(block + 1, block + n + 1); 
        int ans = 1, cnt = 1, tmp = k, left = 1; 
        for(int i = 2; i <= n; i ++){
            if(block[i].color == block[i-1].color){
                cnt ++; 
                tmp -= block[i].pos - block[i-1].pos - 1; 
                while(tmp < 0){
                    cnt --; 
                    tmp += block[left+1].pos - block[left].pos - 1; 
                    left++; 
                }
                ans = max(ans, cnt); 
            }else{
                left = i;
                tmp = k;
                cnt = 1; 
            }
        }
        printf("%d
", ans); 
    }
    return 0; 
}