冶炼金属二分法代码

解题思路:

注意事项:

参考代码:

//冶炼金属：二分

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e4 + 10;

vector<int>a(N);

vector<int>b(N);

int n;

bool check_min(int mid)

{

    for(int i = 0; i < n; i ++)

    {

        if(b[i] < a[i] / mid)

            return false;

    }

    return true;

}

bool check_max(int mid)

{

    for(int i = 0; i < n; i ++)

        if(b[i] > a[i] / mid)

            return false;

    return true;

}

void solve()

{

    cin >> n;

    for(int i = 0; i < n; i ++)

        cin >> a[i] >> b[i];

    //求最小值。

    int lmin = 0, rmin = 1e9;

    while(lmin < rmin)

    {

        int mid = lmin + rmin >> 1;

        if(check_min(mid))

            rmin = mid;

        else

            lmin = mid + 1;

    }

    //求最大值。

    int lmax = 0, rmax = 1e9;

    while(lmax < rmax)

    {

        int mid = lmax + rmax + 1 >> 1;

        if(check_max(mid))

            lmax = mid;

        else

            rmax = mid - 1;

    }

    cout << lmin << " " << lmax << endl;

}

signed main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    solve();

}