ZOJ 3987 Numbers （贪心）

ZOJ 3987 Numbers （贪心）

Description

DreamGrid has a nonnegative integer n. He would like to divide n into m nonnegative integers a1,a2,…,am and minimizes their bitwise or (i.e. n=a1+a2+⋯+am and a1 OR a2 OR … OR am

Input

There are multiple test cases. The first line of input contains an integer TThe first line contains two integers n and m ( 0≤n<101000,1≤m<10100It 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

53 13 23 310000 51244 10

Sample Output

3312000125

题意

将整数 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(); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。