P8647 题解

_xbt · 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;
}