ZOJ 3987 Numbers （贪心）

Description

DreamGrid has a nonnegative integer $n$. He would like to divide $n$ into $m$ nonnegative integers $a_1, a_2, \dots, a_m$ and minimizes their bitwise or (i.e. $n=a_1 + a_2 + \dots + a_m$ and $a_1 \text{ OR } a_2 \text{ OR } \dots \text{ OR } a_m$ should be as small as possible).

Input

There are multiple test cases. The first line of input contains an integer $T$ , indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ( $0 \le n < 10^{1000}, 1 \le m < 10^{100}$ ). It is guaranteed that the sum of the length of does not exceed $20000$ .

Output

For each test case, output an integer denoting the minimum value of their bitwise or.

Sample Input

5
3 1
3 2
3 3
10000 5
1244 10

Sample Output

3
3
1
2000
125

题意

将整数 $n$ 拆分为 $m$ 个数的和，输出这 $m$ 个数 $or$ 的最小值。

思路

考虑贪心，我们知道，$m$ 个数的二进制中某一位有一个为 $1$ ，最终的结果这一位一定是 $1$ ，因此尽可能多的让这 $m$ 个数充满二进制的这一位则为最优。

记录 $n$ 的二进制位数，从高位向低位开始枚举，对于当前位 $i$ ，首先判断 $n$ 是否可以充满 $m$ 行 $i$ 位以下的部分。

• 若可以，则说明溢出部分会被放置在当前位，于是尽可能多的填充当前第 $i$ 位共 $m$ 个二进制位。
• 若不可以，则说明剩余的数字可以被安置在低位，当前位为 $0$ 。

AC 代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    private static Scanner cin;
    static BigInteger n, m;

    public static void solve() {
        int len = 0;
        BigInteger tmp = n;
        while (tmp.compareTo(BigInteger.ZERO) != 0) {
            tmp = tmp.shiftRight(1);
            len++;
        }
        BigInteger ans = BigInteger.ZERO;
        for (int i = len - 1; i >= 0 && n.compareTo(BigInteger.ZERO) > 0; i--) {
            BigInteger cnt = BigInteger.ONE.shiftLeft(i);
            tmp = cnt.subtract(BigInteger.ONE).multiply(m); // 检验n是否可以填满m个低位
            if (tmp.compareTo(n) < 0) { // 若不可以填满则说明当前位一定被占用
                n = n.subtract(cnt.multiply(m.min(n.shiftRight(i)))); // 尽可能多的填充当前位
                ans = ans.or(cnt);
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        cin = new Scanner(System.in);
        int T;
        T = cin.nextInt();
        while ((T--) > 0) {
            n = cin.nextBigInteger();
            m = cin.nextBigInteger();
            solve();
        }
    }
}