蓝桥杯 2023-C-B-3 冶炼金属

点击查看原题

题目描述

小蓝有一个神奇的炉子用于将普通金属O冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V是一个正整数，这意味着消耗 V个普通金

属O恰好可以冶炼出一个特殊金属 X，当普通金属O的数目不足 V时，无法继续冶炼。
现在给出了N条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A个普通金属 O，最终冶炼出了B个特殊金属 X。每条记录都是独立
的，这意味着上一次没消耗完的普通金属O不会累加到下一次的冶炼当中。

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

输入格式

第一行一个整数 N，表示冶炼记录的数目。
接下来输入N行，每行两个整数 A、B，含义如题目所述。

输出格式

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

样例输入

3
75 3
53 2
59 2

样例输出

20 25

题目注释

当 V = 20 时，有：⌊75/20⌋ = 3，⌊ 53/20 ⌋ = 2，⌊ 59/20 ⌋ = 2，可以看到符合所有冶炼记录。
当 V = 25 时，有：⌊75/25⌋ = 3，⌊ 53/25 ⌋ = 2，⌊ 59/25 ⌋ = 2，可以看到符合所有冶炼记录。
且再也找不到比 20 更小或者比 25 更大的符合条件的V值了。

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

代码一

我的方法是通过不断边界判断，找到符合条件的最小值和最大值。

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

#define ll long long
#define vl vector<long long>

void solve() {
  int num;cin >> num;
  vl a(num), b(num);

  for(int i = 0;i< num;++ i){
    cin >> a[i] >> b[i];
  }

  ll min_val = -1, max_val = INT_MAX;

  for(int i = 0;i < num;++ i){
    if(min_val < (a[i] / (b[i] + 1)) + 1) min_val = a[i] / (b[i] + 1) + 1;
    if(max_val > a[i] / b[i]) max_val = a[i] / b[i];
  }

  cout << min_val << " " << max_val << "\n";
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // int _;cin >> _;
  // while(_ --){
    solve();
  // }
  return 0;
}

代码二

二分方法。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e4 + 10;
int n;

int get(int a, int b) {
    int l = 1, r = 1e9 + 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a / mid <= b)
            r = mid;
        else
            l = mid + 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    int minv = 1, maxv = 1e9;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        minv = max(minv, get(a, b));        // 维护最小可能值
        maxv = min(maxv, get(a, b - 1) - 1); // 维护最大可能值
    }

    cout << minv << " " << maxv << "\n";

    return 0;
}