ZOJ- Numbers （贪心，枚举，大数）

ZOJ- Numbers （贪心，枚举，大数）

题面：

题意：

给定大整数(n,m)，让你选择(mathit m)个非负整数(a_1, a_2, dots, a_m)，使其满足：

[n=a_1 + a_2 + dots + a_m ]

问你下式最小是多少？

[a_1 ext{ OR } a_2 ext{ OR } dots ext{ OR } a_m ]

思路：

首先(O(log(n)))算出最小的(cnt,2^{cnt}>n)。

然后我们贪心的来绝定答案的二进制信息中第(mathit i)位取0还是1.

根据贪心思想，我们答案(ans)的第(mathit i) 位若为1时，那么我们尽量让(a_j,jin[1,m]) 的第(mathit i)位都1，这样可以使其sum和更大，后面少一些位取1，答案可以更优。

那么我们枚举(iin[cnt,0])，判断当前是否满足(nleq(2^i-1) imes m)，

若满足，则为了让(ans)更小，该位不取1,让后面位取1足以满足条件。

否则，即：(n>(2^i-1) imes m)代表这(mathit m)个数后面(i-1)位都取1时也无法达到sum和为(mathit n)。

那么(ans)该位就必须取1.同时

[n-=min( floor(frac{n}{2^i-1}),m)*(2^i-1) ]

代码：

import java.math.*;
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		BigInteger zero=BigInteger.valueOf(0);
		BigInteger one=BigInteger.valueOf(1);
	 	BigInteger two=BigInteger.valueOf(2);
		Scanner cin=new Scanner(System.in);
		int t=cin.nextInt();
		for(int icase=1;icase<=t;++icase)
		{
			BigInteger n=cin.nextBigInteger();
			BigInteger m=cin.nextBigInteger();
			BigInteger temp=n;
			int cnt=0;
			while(temp.compareTo(zero)>0)
			{
				cnt++;
				temp=temp.divide(two);
			}
			cnt+=2;
			BigInteger ans=zero;
			BigInteger now;
			BigInteger x;
			for(int i=cnt;i>=0;--i)
			{
				now=two.pow(i).subtract(one);
				if(n.compareTo(now.multiply(m))<=0)
					continue;
				now=now.add(one);
				x=n.divide(now);
				x=x.min(m);
				ans=ans.add(now);
				x=x.multiply(now);
				n=n.subtract(x);
			}
			System.out.println(ans.toString());
		}

	}

}