[CF980C] Posterized

Description

给一个大小为 (n) 的数组,将数值分组,每个组相当于值域的一个子区间,一个组内的数字极差不超过 (k)。压缩后,一个组的数字都会变成这个组中的最小值。求字典序最小的情况。

例如

4 3
2 14 3 4

的结果为 0 12 3 3

Solution

考虑贪心,顺序枚举每一个 (i),对于 (a_i),在值域中,从 (a[i]) 倒序找分组

如果找到了分组,考虑这个分组能否容得下 (a[i]),如果容得下则将 (a[i]) 分进去,否则另开一组

如果没找到分组,则另开一组

原文地址:https://www.cnblogs.com/mollnn/p/12791951.html