ZOJ 3790 Consecutive Blocks 模拟题

先离散一下，然后模拟，把一种颜色i所在的位置都放入G[i]中。然后枚举一下终点位置，滑动窗体使得起点和终点间花费不超过K，求中间过程的最大值就可以。

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

#define N 100005

set<int>myset;

map<int,int>mp;

set<int>::iterator p;

int n ,k;

int a[N];

vector<int>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<int,int>(*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<top;i++)

			ans = max(ans, go(i));

		printf("%d\n",ans);

	}

	return 0;

}

/*

13 3

1000000000 2 2 1 1 2 2 5 6 8 2 2 2

*/

秒客网

ZOJ 3790 Consecutive Blocks 模拟题

相关文章