蓝桥杯2023年第十四届省赛真题-冶炼金属—二分算法

解题思路:求最大值和最小值，可以考虑二分

注意事项:

参考代码:

#include<iostream>

using namespace std;

long long a[10005][3],n;

int check1(long long x)

{

    long long i;

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

    {

        if(a[i][0]/x>a[i][1])

            return 0;

    }

    return 1;

}

int check2(long long x)

{

    long long i;

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

    {

        if(a[i][0]/x<a[i][1])

            return 0;

    }

    return 1;

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0);

    long long i,j;

    cin>>n;

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

    {

        for(j=0;j<2;j++)

            cin>>a[i][j];

    }

    long long l=1,r=1e9;

    long long mid,ans1=0,ans2=0;

    while(l<=r)

    {

        mid=(l+r)/2;

        if(check1(mid))

        {

            ans1=mid;

            r=mid-1;

        }

        else

            l=mid+1;

    }

    l=1;

    r=1e9;

    while(l<=r)

    {

        mid=(l+r)/2;

        if(check2(mid))

        {

            ans2=mid;

            l=mid+1;

        }

        else

            r=mid-1;

    }

    cout<<ans1<<' '<<ans2;

    return 0;

}