CF1188D

· · 题解

真是一道神题啊 .

首先找到最大值，不难发现操作只会让数变大所以一种合法的操作方案肯定是先操作几次最大值然后把所有数都变到最大值 .

若操作完的最大值是 M，则代价显然就是

\operatorname{cost'}(M) = \sum_{i=1}^n\operatorname{popcount}(M-a_i)

其中 \operatorname{popcount}(x) 表示 x 二进制中 1 的个数 .

于是我们的目标就是找到一个 \displaystyle M\ge \max_i\{a_i\} 使得 \operatorname{cost}(M) 最小 .

这个 M 不小于最大值的限制很难搞，考虑把它去掉 .

我们发现 \{a\} 的顺序不会影响答案，于是先把 \{a\} 排序，则令 m=M-a_n，于是

\operatorname{cost}(m) = \sum_{i=1}^n\operatorname{popcount}(m+a_n-a_i)

令 b_i=a_n-a_i，则

\operatorname{cost}(m) = \sum_{i=1}^n\operatorname{popcount}(m+b_i)

这样就没有限制了（当然 m\in \N^+ 这个条件自然是有的）.

我们考虑 \operatorname{popcount} 的贡献，显然是要按位考虑，于是我们要记录下面几个信息：

这个进位比较难维护，但是发现每次加的 m 是定值，于是 b_i 这位后面的位数越大越可能进位 .

形式化的，如果目前枚举到第 k 位，则 b_i\bmod 2^k 越大进位越多 .

我们发现影响目前位的肯定是一段前缀进位，于是 DP，令 dp_{i,j} 表示目前算到第 i 位，目前有 j 个 a_k 产生进位的答案 .

因为 b_i\bmod 2^k 越大进位越多，所以我们钦定 b_i\bmod 2^k 最大的 j 个进位即可，这样就随便转移了 .

于是时间复杂度为 O(\operatorname{sort}(n)\log V)，其中 \operatorname{sort}(n) 为整数排序复杂度，V 是值域 .

CF Submission: 161519373 .