整数二分答案
时间复杂度 $O(nlogn)$
思路:
首先我们能想到,巧克力边长肯定是在一个区间内的,是可枚举的。看一下题目数据范围边长 $<=1e5$ 而且题目说了至少能切出 $1\times1$的巧克力,所以答案肯定是在 $[1,100000]$范围内的。那么我们就可以二分了。
- 二分模板的选择
参考Y总的二分模板yxcの二分
这里我们用第二个模板:
当check(mid)满足条件时,也就是分得的巧克力数大于等于k时,那么左边的区间肯定也是满足的,并且mid也是可取的,所以l = mid
。
当不满足时,很显然答案肯定在我们分得的区间左边,因为mid已经不满足了,所以我们的r = mid-1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,k;
struct Node {
int x,y;
}node[N];
bool check(int x) {
int res = 0;
for (int i = 0; i < n; i ++) {
res += (node[i].x/x)*(node[i].y/x);
}
return res >= k;
}
int main() {
scanf("%d%d",&n,&k);
for (int i = 0; i < n; i ++) scanf("%d%d",&node[i].x,&node[i].y);
int l = 1,r = 1e5;
while(l < r) {
int mid = l+r+1>>1;
if(check(mid)) l = mid;
else r = mid-1;
}
cout << l << endl;
return 0;
}
Java代码
import java.util.*;
import java.io.*;
public class Main {
static int n, m;
static int[] h = new int[100010];
static int[] w = new int[100010];
public static boolean check(int x) {
int res = 0;
for (int i = 0; i < n; i ++) {
res += (h[i]/x)*(w[i]/x);
}
return res >= m;
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();m = sc.nextInt();
for (int i = 0; i < n; i ++) {
h[i] = sc.nextInt();
w[i] = sc.nextInt();
}
int l = 1,r = 100000;
while(l < r) {
int mid = l+r+1>>1;
if(check(mid)==true) l = mid;
else r = mid-1;
}
System.out.println(l);
}
}
大佬牛批