G - Numbers ZOJ - 3987 (large number + greed)

Topic link~~~~~

I can't shake the pot this time.

First of all, let's talk about the meaning of the question, which is to divide a number into m groups to make their number or the smallest.

Analysis:

At the beginning, I thought it was too simple. It was a little preconceived. Although I thought that the average binary bit would make the or value minimum, I couldn't deal with it when I couldn't exactly average it

. Self closing

Next is the focus:

We can divide them according to their positions,

First of all, if we want to find his highest position, if (2 * k - 1) * m > n > (2 * (k-1) - 1) * m, then we must assign the k-bit to 1. Why? You can think about (2 * k - 1) * m, and if you don't divide it, it will exceed M.

Then we'll see how many parts it can be divided into at most, and we'll keep subtracting until we've finished.

First, java large number code, save a board:

import java.math.BigInteger;
import java.util.Scanner;
 
public class Main 
{
	public static BigInteger two = BigInteger.valueOf(2);
	public static BigInteger one = BigInteger.ONE;
	public static BigInteger zero = BigInteger.ZERO;
	public static BigInteger n, m;
	public static BigInteger a[] = new BigInteger[4005];
	public static void init()
	{
		a[0] = one;
		for(int i = 1; i <= 4002; i++)
			a[i] = a[i - 1].multiply(two);
	}
	public static void main(String[] args) 
	{
		Scanner cin = new Scanner(System.in);
		int t = cin.nextInt();
		init();
		while(t > 0)
		{
			t--;
			int up = 0;
			n = cin.nextBigInteger();
			m = cin.nextBigInteger();
			BigInteger sum = zero, temp = n, ans = zero;
			for(int i = 0; sum.compareTo(n) < 0; i++)
			{
				sum = sum.add(m.multiply(a[i]));
				up = i;
			}
			for(int i = up; i >= 0; i--)
			{
				BigInteger b = a[i].subtract(one);
				//if(T.multiply(m).compareTo(temp) >= 0) continue;
				if((b.multiply(m)).compareTo(temp) >= 0) continue;
				BigInteger k = temp.divide(a[i]); // It can be divided into several parts
				k = k.min(m);
				ans = ans.add(a[i]);
				temp = temp.subtract(a[i].multiply(k)); // Subtract
			}
			System.out.println(ans);
		}
		cin.close();
	}
}

python code: what's hard is that I'm forgetting about python 2. X, 3.x syntaxorz

t = int(input())
while t > 0:
    t -= 1
    a, b = map(int, raw_input().split())
    num = 1
    ans = 0
    while (num - 1) * b <= a:
        num *= 2
    while a > 0:
        while (num - 1) * b >= a:
            num /= 2
        ans += num
        if num * b < a:
            a -= num * b
        else:
            a = a % num
    print ans

 

Tags: Java Python

Posted on Fri, 29 Nov 2019 10:34:37 -0800 by CaseyC1