论坛 › IT职场那些事 › [蓝桥杯]真题解说：冶炼金属（暴力+二分）

去皮卡多 发表于 2025-3-25 01:40:07

[蓝桥杯]真题解说：冶炼金属（暴力+二分）

一、视频解说

视频解说
https://i-blog.csdnimg.cn/blog_migrate/6cc8084d5b9607922f6507c7b5fa3b2a.png
二、暴力代码

//暴力代码
#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e4 + 10;

void solve()
{
        int n; cin >> n;
        vector<int>a(n), b(n);//创建数组
        for(int i = 0; i < n; i ++)
                cin >> a >> b;

        for(int i = 1; i <= 1e6; i ++)//枚举的转化率V
        {
                bool flag = true;//标记一下当前的V是否合法

                for(int j = 0; j < n; j ++)
                {
                        if(b != (a / i))
                        {
                                flag = false;
                                break;
                        }
                }
                if(flag)
                {
                        cout << i << " ";
                        break;
                }
        }
       
        for(int i = 1e6; i >= 1; i --)
        {
                bool flag = true;
                for(int j = 0; j < n; j ++)
                {
                        if(b != (a / i))
                        {
                                flag = false;
                                break;
                        }
                }
                if(flag)
                {
                        cout << i << " ";
                        break;
                }
        }

       
}

signed main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int t;
        t = 1;
        //cin >> t;
        while(t--)
        solve();
}

三、正解代码

//冶炼金属：二分
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10;
int a, b;
int n;

bool check_min(int mid)
{
        for(int i = 0; i < n; i ++)
        {
                if(b < a / mid)
                        return false;
        }

        return true;
}

bool check_max(int mid)
{
        for(int i = 0; i < n; i ++)
                if(b > a / mid)
                        return false;

        return true;
}

void solve()
{
        cin >> n;
        for(int i = 0; i < n; i ++)
                cin >> a >> b;

        //求最小值。
        int lmin = 1, rmin = 1e9;
       
        while(lmin < rmin)
        {
                int mid = lmin + rmin >> 1;
                if(check_min(mid))
                        rmin = mid;
                else
                        lmin = mid + 1;
        }

        //求最大值。
        int lmax = 1, 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);
        int t = 1;
        // cin >> t;
        while(t--)
        solve();
}



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

查看完整版本: [蓝桥杯]真题解说：冶炼金属（暴力+二分）