冶炼金属

题目：冶炼金属

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。

这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。

现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。

每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 N，表示冶炼记录的数目。

接下来输入 N 行，每行两个整数 A、B，含义如题目所述。

输出格式

输出两个整数，分别表示 V 可能的最小值和最大值，中间用空格分开。

数据范围

对于 30% 的评测用例，1≤N≤102。对于 60% 的评测用例，1≤N≤103。
对于 100% 的评测用例，1≤N≤104，1≤B≤A≤109。

输入样例：

3
75 3
53 2
59 2

输出样例：

20 25

样例解释

当 V=20 时，有：⌊7520⌋=3，⌊5320⌋=2，⌊5920⌋=2，可以看到符合所有冶炼记录。

当 V=25 时，有：⌊7525⌋=3，⌊5325⌋=2，⌊5925⌋=2，可以看到符合所有冶炼记录。

且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。

解题思路：

​ 读过题目后，可以发现题目需要分别找到一个最大值和最小值满足所给条件，而且对于找到的值，我们可以通过判断，能判断出它是大于我们的答案还是小于我们的答案，存在二段性，故可以采用二分做。

​ check函数的书写，对于每个需要检查的值，我们通过其与所有组的数据进行判断：

int t = a[i] / x;

if (t < b[i]) return 1 //说明我们找到的这个数太大了，以至于不能转化出的金属不足要求
if (t > b[i]) return 3 //说明我们找到的这个数太大了，以至于转化出的金属超量

//如果所有的数据都没有出现上述情况，则说明当前这个数，是我们要找的答案
return 1

​

AC代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int a[N], b[N];

int check(int x)
{
    for (int i = 1; i <= n; i ++)
    {
        int t = a[i] / x;
        if (t > b[i]) return 2;
        if (t < b[i]) return 3;
    }
    
    return 1;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
    
    int l = 1, r = 1e9;
    while (l < r)
    {
        int mid = l + r >> 1;
        int t = check(mid);
        if (t == 1 || t == 3) r = mid;
        else l = mid + 1;
    }
    
    cout << l << " ";
    l = 1, r = 1e9;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        int t = check(mid);
        if (t == 1 || t == 2) l = mid;
        else r = mid - 1;
    }
    
    cout << l << " ";
    return 0;
}

Go版本

package main

import (
	"bufio"
	"fmt"
	"os"
)

const N int = 10010

var n int
var a, b [N]int
var in = bufio.NewReader(os.Stdin)

func main() {
	fmt.Fscan(in, &n)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &a[i], &b[i])
	}
	l, r := 1, int(1e9)
	for {
		if l >= r {
			break
		}
		mid := (l + r) / 2
		t := check(mid)
		if t == 1 || t == 3 {
			r = mid
		} else {
			l = mid + 1
		}
	}
	fmt.Printf("%d ", l)
	l, r = 1, int(1e9)
	for {
		if l >= r {
			break
		}
		mid := (l + r + 1) / 2
		t := check(mid)
		if t == 1 || t == 2 {
			l = mid
		} else {
			r = mid - 1
		}
	}
	fmt.Printf("%d", l)
}

func check(x int) int {
	for i := 1; i <= n; i++ {
		t := a[i] / x
		if t > b[i] {
			return 2
		}
		if t < b[i] {
			return 3
		}
	}
	return 1
}