oiclass特殊石子题解

xiaoxiaoyyds · 2025-09-22 19:30:35 · 题解

特殊石子
考虑贪心加二分，先二分要多少次操作，假如之后还要操作 k 次，将最大的 a_i 减去 2^k ，重复直到删空。
考虑一个数要几次删空，记为 s ，将序列以 s，从大到小排，则答案最多为 s_i + i 的最大值。
发现答案最多减一，考虑优化。
发现只有 m 个数字不会被一次删掉，因此只需要保留 m 个最小的数字，将这些数按最高位分为 m 个集合，我们从大到小操作，设集合内最高位为 2^x 则最小的数字至少要 x 此操作，则倒数第二个数至少要 x+1 次，而最高位为 2^x ，可以一次删掉，因此只有最小有用。
可以直接拿莫队+set维护前m个，其他东西可以预处理一下。