题目链接:http://codeforces.com/problemset/problem/180/E
题目大意:
有n个方块,m种颜色,k次机会。
每个方块染了一种颜色,现在你可以最多消除k个方块。使相同颜色的连续方块最多。
思路:用vector记录每种方块的位置,对每个颜色进行尺取就可以了。
#include <bits/stdc++.h>
using namespace std;
vector<int> v[100005];
int main(){
int n, m, k, x;
scanf("%d%d%d", &n, &m, &k);
for(int i=1; i<=n; i++){
scanf("%d", &x);
v[x].push_back(i);
}
int MAX=0;
for(int i=1; i<=m; i++){
int Len=v[i].size();
int L=0, R=0, cut=0;
while(R>=L&&R<Len){
if(cut>k){
cut-=v[i][L+1]-v[i][L]-1;
L++;
}
else{
if(R+1<=n)
cut+=v[i][R+1]-v[i][R]-1;
MAX=max(MAX, R-L+1);
R++;
}
}
}
printf("%d\n", MAX);
return 0;
}