AcWing 1227. 分巧克力
原题链接
简单
作者:
完全多重共线性
,
2024-02-28 22:39:33
,
所有人可见
,
阅读 20
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int N = 100010,M = 1,INF = 0x3f3f3f3f,MOD = 1e9 + 7;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
int n,m;
LL sum;
int a[N],b[N];
bool check(int mid)
{
int cnt = 0;
for(int i = 0;i < n;i ++)
cnt += (a[i] / mid) * (b[i] / mid);
if(cnt >= m) return true;//如果可以切的数大于目标值 就说明边长有可能可以更长 就往大了切
else return false; //反之 往小了切
}
void solve()
{
cin >> n >> m;
for(int i = 0;i < n;i ++) cin >> a[i] >> b[i];
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 << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
// int t = 1;
int t;cin >> t;
while(t -- ) solve();
return 0;
}