AcWing 1227. 分巧克力

Problem: AcWing 1227. 分巧克力

思路

这是一个二分查找的问题。我们需要找到最大的边长m，使得我们可以从巧克力板中切出至少k块边长为m的正方形巧克力。我们可以通过二分查找来找到这个最大的边长。我们从最小边长1开始，到最大边长r（r为所有巧克力板的最大边长），然后在这个范围内进行二分查找。对于每一个中间值，我们检查是否可以从巧克力板中切出至少k块边长为m的正方形巧克力。如果可以，我们就将左边界移动到中间值的右边，否则我们将右边界移动到中间值的左边。最后，我们找到的右边界就是我们需要的最大边长。

解题方法

我们使用二分查找的方法来解决这个问题。对于每一个中间值，我们计算每块巧克力板可以切出多少块边长为m的正方形巧克力，然后将这些数量相加。如果总数量大于等于k，那么我们就知道这个边长是可以的，我们需要增大边长。如果总数量小于k，那么我们就知道这个边长是不够的，我们需要减小边长。

复杂度

时间复杂度:

二分查找的时间复杂度为$O(\log n)$，对于每一个中间值，我们需要$O(n)$的时间来计算每块巧克力板可以切出多少块边长为m的正方形巧克力，所以总的时间复杂度为$O(n\log n)$。

空间复杂度:

我们只需要$O(n)$的空间来存储每块巧克力板的长和宽，所以空间复杂度为$O(n)$。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main{
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int MAXN = (int) (1e5 + 10);
	static int[][] arr = new int[MAXN][2];
	static int n, k;

	public static void main(String[] args) throws IOException {
		n = nextInt();
		k = nextInt();
		int l = 1, r = 0, ans = 0;
		for (int i = 0; i < n; i++) {
			arr[i][0] = nextInt();
			arr[i][1] = nextInt();
			r = Math.max(arr[i][0], arr[i][1]);
		}
		while (l <= r) {
			int m = (l + r) >> 1;
			if (check(m)) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		out.println(ans);
		out.flush();

	}

	private static boolean check(int m) {
		// TODO Auto-generated method stub
		int ans = 0;
		for(int i = 0; i < n; i++) {
			ans += (arr[i][0] / m) * (arr[i][1] / m);
		}
		if(ans >= k) {
			return true;
		}
		return false;
	}

	private static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}