自动搬运

查看原文

来自洛谷，原作者为

	_xbt 蒟蒻一个||支持互关

搬运于2025-08-24 22:41:02，当前版本为作者最后更新于2023-04-21 22:23:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

因为这道题中 $N$ 和 $K$ 都较大，暴力枚举必然超时，所以想到二分答案。

那么二分答案行不行呢，我们通过观察发现答案具有单调性，我们就可以使用二分答案。所有可能的边长为 $1$ 到 $10^5$，每次判断当前边长是否满足 $K$。若满足，则 $l$ 更新，不满足则 $r$ 更新。

对于第 $i$ 块巧克力，当边长为 $x$ 时，可以分出 $\left\lfloor (a_i \div x) \times (b_i \div x) \right\rfloor$ 块巧克力。

$\text{code}$

#include<iostream>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int n,k,a[100010],b[100010];
int check(int x){
	int ans=0;
	for(int i=0;i<n;i++) ans+=(a[i]/x)*(b[i]/x);
	return ans>=k;
}
int main(){
	IOS;
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>a[i]>>b[i];
	int l=1,r=100000;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l;
}