AcWing 1227. 分巧克力
原题链接
简单
作者:
ofs
,
2024-04-11 23:45:27
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
#define longlong int
#define endle '\n'
#define INF 0x3f3f3f3f3f3f
using namespace std;//!!!!!!!!!!!别忘了写
const int N=1e5;
int h[N],w[N];
int n;
int k;
int a;
bool fine(int a)
{
int amount=0;
int i;
for(i=0;i<n;i++)
{
//长除以a代表可以有几列a,宽除以a可以代表有几行a
//比如6X5的矩阵 a=3 6/3=2 5/3=1 代表最多有21=2个33的矩阵,可以画个tu
amount+=(h[i]/a)*(w[i]/a); //同时满足了对巧克力长宽的要求,并且可以求出来块数
}
if(amount>=k) return true;
else return false;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k; //有几块
int i;
int H[n],W[n];
for(i=0;i<n;i++)
{
cin>>h[i]>>w[i];
H[i]=h[i];
W[i]=w[i];
}
int r1,r2;
int l=1,r;
sort(H,H+n);sort(W,W+n);
r1=H[n-1];r2=W[n-1];
r=max(r1,r2);
int amax;
while(l<r)
{
amax=l+r+1>>1;
if(fine(amax)) l=amax;
else r=amax-1;
}
cout<<l<<endl;
return 0;
}