CF980C Posterized

先来吐槽一下这个 sb 翻译，根本就没做过题吧……

大概就是让你给值域分成连续的几组，每组大小不能超过 \(k\)，然后将序列中的值全部替换成其组内的最小值，要使得序列的字典序最小。

因为是字典序，所以越前面的值要尽量小。对于还未处理过的第一个值，找到能包含它的最小值，然后暴力分组。

时间复杂度 \(O\left(nk\right)\)。

code:

#include<bits/stdc++.h>

using namespace std;

#define Max(x,y)((x)>(y)?x:y)

#define For(i,x,y)for(i=x;i<=(y);i++)

#define Mems(i,j)memset(i,j,sizeof i)

int p[100005],a[256];

//a 数组表示每个值分的组中的最小值

int main()

{

	int n,k,i,j,l;

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

	For(i,1,n)scanf("%d",&p[i]);

	Mems(a,-1);

	For(i,1,n)

	if(!~a[p[i]])

	For(j,Max(p[i]-k+1,0),p[i])

	if(!~a[j]||p[i]-a[j]<k)

	{

		For(l,j,p[i])a[l]=j;

		break;

	}

	For(i,1,n)printf("%d ",a[p[i]]);

	return 0;

}

巴特西

CF980C Posterized

最新文章

热门文章