题解：CF1893D Colorful Constructive

· · 题解

难点在于你要有十足的把握你的算法是正确的，而不是瞎胡了一个上去然后吃 100 发。

vp 的时候想了一个做法，把架子按照 d_i 分块，然后大体上是按照长度降序排，然后最后的散块的长度当成 d_i。

然后按照出现次数从大到小枚举颜色。

但是这个东西会被形如

6 2
1 1 1 2 2 2
3 3 
2 2

给叉掉，因为你直接分配可能有点问题。

后来发现假了，考虑仍然是分块，然后你在填的时候你不考虑相邻块的同色限制。

你先填好，如果能填就一定有解。

你接下来对每个架子，重新分配颜色。这时候假如你的 s=10, d=2 是这样

1 2 3 4 | 5 6 7 8 | 9 10

那你按照 

9  5  1  10  6  2  7  3  8  4

的顺序枚举位置，按照颜色出现次数从大到小填进去就行。

这是一定有解的，因为你一开始已经保证了一种方案使得块内互不相同。你接下来填的时候在此基础上，这种遍历方式还能使得块间不同。

时间复杂度线性对数。