【贪心】Codeforces Round #480 (Div. 2) C. Posterized

题意：让你对[0,255]这个序列任意划分成一些不重叠的子段，每个子段的大小不超过K。给你n个不超过255的数，让你将每个数替换成它所在子段的任意一个元素，使得最终这个n个数的序列的字典序最小。

p[x]代表x作为代表元素的话，其所控制的区间的最后一个元素是谁。

读入一个数a的时候，在[0,255]数轴上找它前面的离它最近的一个已被标记的数b，如果与其的距离不超过K，则a的代表元素就是b，然后将p[b]更新成max(p[b],a)。

如果b与a的距离比K还大，就把控制a的元素记为c=max(a-K+1,p[b]+1)，因为我们不能涉及b已经控制的区间。然后把p[c]更新为a。

#include<cstdio>

#include<algorithm>

using namespace std;

int n,K,p[256];

bool b[256];

int main(){

	int x,t,tt;

	scanf("%d%d",&n,&K);

	for(int i=1;i<=n;++i){

		scanf("%d",&x);

		t=-1;

		for(int j=x;j>=0;--j){

			if(b[j]){

				t=j;

				break;

			}

		}

		if(t==-1){

			if(x>=K){

				b[x-K+1]=1;

				p[x-K+1]=x;

				printf("%d%c",x-K+1,i==n ? '\n' : ' ');

			}

			else{

				b[0]=1;

				p[0]=x;

				printf("0%c",i==n ? '\n' : ' ');

			}

		}

		else if(t+K-1<x){

			tt=max(x-K+1,p[t]+1);

			b[tt]=1;

			p[tt]=x;

			printf("%d%c",tt,i==n ? '\n' : ' ');

		}

		else{

			p[t]=max(p[t],x);

			printf("%d%c",t,i==n ? '\n' : ' ');

		}

	}

	return 0;

}

巴特西

【贪心】Codeforces Round #480 (Div. 2) C. Posterized

最新文章

热门文章