题目地址:http://codeforces.com/contest/980/problem/C

官方题解:

 

题解:一共256个像素网格,可以把这个256个分组,每个分组大小<=k。给出n个像素格子,要求每个像素用分组里的一个数表示,并且表示出来的字典序要最小。

 

方法:先把数组a全部赋值为-1,表示数组的这个数未分组。然后一个个数字扫进来,如果这个数字没有分组的话,我们找到这个组的范围max(0,p-k+1)~p,如果前面的最小数字未分组或者分组的情况是它自己的话,我们就从前面最小的数字到p分组为最小的数字。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<string>
 6 #include<iostream>
 7 #include<map>
 8 #include<vector>
 9 #include<set>
10 #include<queue>
11 using namespace std;
12 int main() 
13 {
14     int a[257],n,k;
15     for (int i = 0; i < 257; i++)    a[i] = -1;
16     scanf("%d %d", &n, &k);
17     for (int i = 0; i < n; i++)
18     {
19         int p;
20         scanf("%d", &p);
21         if (a[p] == -1)
22         {
23             for (int j = max(0, p - k + 1); j <= p; j++)
24             {
25                if (a[j] == -1 || a[j] == j)
26                {
27                     for (int k = j; k <= p; k++) 
28                         a[k] = j;
29                     break;
30                 }
31             }
32         }
33         printf("%d", a[p]);
34         if (i != n - 1) printf(" ");
35         else printf("\n");
36     }
37     return 0;
38 }