Consecutive Blocks
先离散一下，然后模拟，把一种颜色i所在的位置都放入G[i]中，然后枚举一下终点位置，滑动窗口使得起点和终点间花费不超过K，求中间过程的最大值即可。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define N 100005 set myset; map mp; set ::iterator p; int n ,k; int a[N]; vector s[N]; int go(int cur){ int now = k; int ans = 1, l = 0, siz = s[cur].size(); int len = 1; for(int i = 1; i < siz; i++){ if(s[cur][i-1] == s[cur][i]-1) { len++; ans = max(ans, len); continue; } now -= s[cur][i]-s[cur][i-1]-1; if(now>=0) { len++; ans = max(ans, len);} else { while(now<0) { l++; now += s[cur][l]-s[cur][l-1]-1; len--; } len++; } } return ans; } int main() { int T ,m,u,v,w, i ,j; while(~scanf("%d %d",&n,&k)){ myset.clear(); mp.clear(); for(i=1;i<=n;i++)scanf("%d",&a[i]),myset.insert(a[i]); for(p=myset.begin(), i = 1; p!=myset.end(); p++, i++) mp.insert(pair (*p,i)),s[i].clear(); int top = i; for(i=1;i<=n;i++) { a[i] = mp.find(a[i])->second; s[a[i]].push_back(i); } int ans = 0; for(i=1;i