---
title: "3、冶炼金属"
created: 2025-11-28
tags:
  - 算法
---

# 3、冶炼金属

## 题目 [冶炼金属](https://www.acwing.com/problem/content/description/4959/)

![[image-f0f85016.png]]

## 思路分析

![[image-8446480f.png]]

![[image-d855f6e1.png]]

![[image-a8805a9a.png]]

v个o可以冶炼出一个x

令o为o的个数 x为x的个数

其实就有o/v=x

这个v可以取到很多 比如o=75时 x=3时 v可以取20~25

有明显的满足条件的范围 典型二分问题

我可以对每组询问都二分去求出v\*min 和 v\*max

但是答案应该是满足所有情况的 那就是要取交集

也就是说要在所有的v\*min里面找一个最大的 所有的v\*max里找一个最小的

用这两句实现即可

$vmin=max(vmin,findleft(o,x)); vmax=min(vmax,findright(o,x));$

重点在于怎么二分找到这个v\*min和v\*max

![[image-5609b20e.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;cin>>n;
    int maxv=1e9,minv=1;
    while(n--){
        int A,B;cin>>A>>B;
        int l=1,r=A;
        while(l<r){
            int m=l+r>>1;
            if(A/m<=B)  r=m;
            else    l=m+1;
        }
        minv=max(minv,r);

        l=1,r=A;
        while(l<r){
            int m=l+r+1>>1;
            if(A/m>=B)  l=m;
            else    r=m-1;
        }
        maxv=min(maxv,r);
    }
    cout<<minv<<" "<<maxv;
    return 0;
}
```

```cpp
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'

int findleft(int o,int x)
{
    int l=1,r=1e9;
    while(l<r)
    {
        int mid=l+r>>1;
        if(o/mid<=x)
            r=mid;
        else
           l=mid+1;
    }
    return r;
}

int findright(int o,int x)
{
    int l=1,r=1e9;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(o/mid>=x)
            l=mid;
        else
            r=mid-1;
    }
    return r;
}

int main()
{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
 cin>>n;
    int v_min=1,v_max=1e9;
    while(n--)
    {
        int o,x;
        cin>>o>>x;
        v_min=max(v_min,findleft(o,x));
        v_max=min(v_max,findright(o,x));
    }
    cout<<v_min<<" "<<v_max;
    return 0;
}
```

## 同类题型

## 视频讲解

- [[2-Learning/02-算法/03-刷题理模型/历年真题 模考特训/第十四届 c++ B组 省赛/3、冶炼金属|3、冶炼金属]]

---
⬅️ [[00-刷题理模型]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/二分相关模型/5、四平方和|5、四平方和]]