选取方式：CF *3000+ 按通过人数排序。
CF1188D Make Equal
记 \(cnt(x)\) 表示 \(x\) 二进制下 \(1\) 的个数，题目等价于求 \(x\) 使得
\[\sum_{x=1}^n cnt(x + a_n - a_i) \]最小。
令 \(a_i = a_n - a_i\)。
从低位到高位考虑，假设当前要决策第 \(k\) 位，我们需要知道:
\(1.\) \(x\) 在这一位的值
\(2.\) \(a_i\) 在这一位的值
\(3.\) 之前的决策引起的进位
其中第三部分比较棘手，但是如果不考虑更高的位，那么 \(\mod 2^{k}\) 越大的 \(a\) 显然越容易进位，于是我们在每一位的决策是把所有 \(a\) 按 \(\mod 2^{k}\) 从大到小排序，那么进位的一定是一个前缀，直接枚举这个前缀，设 \(f_{i,j}\) 表示考虑前 \(i\) 位，第 \(i\) 位有 \(j\) 个进位的最小答案，简单讨论转移，时间复杂度 \(O(n \log n \log a)\)。
总结：
- 可以先设计一个暴力 dp 状态（实际上笔者在做题时先想到了按 \(\mod 2^k\) 分类，但是误以为是贪心，导致没有做出本题）
- 利用偏序关系化简状态，某些指数级的状态按顺序做就可能降为多项式级别