题意:
255个像素格子,可以把这个255个分组,每组的大小不能超过k。
给出n个像素,要求每个像素用这组的key代表,并且表示出来的字典序要最小。
思路:
感谢js教本智障。
很自然的会想到贪心,也就是说,每次对当前的数,都要找到最小的可以当它的key的数。
那么这种数只能有两种情况,一种是这个数还没有使用过,另一种就是这个数是自己的key,其它情况都不满足。
比如
4 3
2 14 3 4
2找到0,然后把0到2的key都变为0;
找3的时候,由于1,2已经被使用,所以3只能找到自己。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for (int i = ;i < ;i++) a[i] = -;
while (n--)
{
int x;
scanf("%d",&x);
if (a[x] == -)
{
for (int i = max(,x-k+);i <= x;i++)
{
if (a[i] == - || a[i] == i)
{
for (int j = i;j <= x;j++) a[j] = i;
break;
}
}
}
printf("%d ",a[x]);
}
return ;
}