蓝桥杯c/c++程序设计——冶炼金属

?冶炼金属

问题描述

小蓝有一个神奇的炉子用于将普通金属?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?值了。

评测用例规模与约定

对于?3030% 的评测用例，1≤N≤10^2。

对于?6060% 的评测用例，1≤N≤10^3。

对于?100100% 的评测用例，1≤N≤10^4，1≤B≤A≤10^9。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M
PyPy3	3s	256M
Go	3s	256M
JavaScript	3s	256M

?代码一：

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a,b,sun,sun2,min=1e9+1,max=0;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        sun=a/b;
        sun2=a/(b+1)+1;
        if(sun<min) min=sun;
        if(sun2>max) max=sun2;
    }
    cout<<max<<" "<<min;
    return 0;
}

?

#include<iostream>
using namespace std;

这两行代码包含了输入输出流的标准库，并指明使用?std?命名空间。

const int N=1e9+1
int main()
{

这里定义了一个常量?N，并初始化为 10^9 + 1。接着是?main?函数的开始。

    int n;
    cin >> n;

声明了一个整型变量?n，并从标准输入读取一个整数存储到变量?n?中。

    int a[N],b[N],c[N],d[N];

声明了四个长度为?N（非常大）的整型数组?a、b、c、d。

    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
        c[i] = a[i] / b[i];
        d[i] = a[i] / (b[i] + 1) + 1;
    }

循环?n?次，每次读取两个整数并分别存储到?a[i]?和?b[i]?中，然后分别计算?a[i] / b[i]?的结果并存储在?c[i]?中，计算?a[i] / (b[i] + 1) + 1?的结果并存储在?d[i]?中。

    int min = c[0], max = d[0];

初始化了两个变量?min?和?max?分别为?c[0]?和?d[0]。

    for (int i = 0; i < n; i++)
    {
        if (c[i] < min) min = c[i];
        if (d[i] > max) max = d[i];
    }

再次循环?n?次，每次对?c[i]?和?d[i]?分别进行比较，更新?min?和?max?的值。

    cout << max<<" "<< min;

输出?max?和?min。

    return 0;
}

返回 0，表示程序正常结束。

代码分析：?

1. #include<iostream>：这行代码包含了输入输出流的标准库，使得可以使用?cin?和?cout。

2. using namespace std;：这行代码表示使用标准命名空间，这样我们就可以直接使用?cin?和?cout?而不需要加上?std::?前缀。

3. const int N=1e9+1：这行代码定义了一个常量?N，并赋值为 1 亿零 1。

4. int main()：这行代码声明了程序的入口点，即?main?函数。

5. int n;：这行代码声明了一个整型变量?n，用来存储输入的数量。

6. cin >> n;：这行代码从标准输入读取一个整数并存储到变量?n?中。

7. int a[N],b[N],c[N],d[N];：这行代码定义了四个长度为?N?的整型数组?a、b、c、d，这里要注意?N?非常大，可能会超出栈内存，建议使用动态内存分配。

8. for (int i = 0; i < n; i++)：从 0 循环到 n-1。

9. { cin >> a[i] >> b[i]; c[i] = a[i] / b[i]; d[i] = a[i] / (b[i] + 1) + 1; }：循环体内部从输入中读取两个整数，分别存储在?a[i]?和?b[i]?中，然后分别计算?a[i] / b[i]?的结果并存储在?c[i]?中，计算?a[i] / (b[i] + 1) + 1?的结果并存储在?d[i]?中。

10. int min = c[0], max = d[0];：定义了两个变量?min?和?max，并分别初始化为?c[0]?和?d[0]。

11. for (int i = 0; i < n; i++)：又一个循环，这次也从 0 循环到 n-1。

12. if (c[i] < min) min = c[i]; if (d[i] > max) max = d[i];：在循环中对?c[i]?和?d[i]?分别进行比较，更新?min?和?max?的值。

13. cout << max<<" "<< min;：输出?max?和?min。

14. return 0;：返回 0，表示程序正常结束。

?

代码二：

#include<iostream> // 引入iostream头文件，用于输入输出流
using namespace std; // 命名空间

int main()
{
    int n; // 声明变量n，用于表示输入的数对的个数
    cin >> n; // 输入n的值

    int a[100001], b[100001], c[100001], d[100001]; // 声明四个数组a、b、c、d，大小为100001

    // 循环读取n个数对
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i]; // 输入第i个数对的值
        c[i] = a[i] / b[i]; // 计算c[i]
        d[i] = a[i] / (b[i] + 1) + 1; // 计算d[i]
    }

    int min = c[0], max = d[0]; // 初始化最小值和最大值为数组c和d的第一个元素

    // 遍历数组c和d，找到最小值和最大值
    for (int i = 0; i < n; i++)
    {
        if (c[i] < min) min = c[i]; // 如果c[i]小于最小值，更新最小值
        if (d[i] > max) max = d[i]; // 如果d[i]大于最大值，更新最大值
    }

    cout << max<<" "<< min; // 输出最大值和最小值

    return 0; // 返回0，表示程序正常结束
}

注意事项：

当 V=20?时，有：?75/20?=3?，?53/20?=2，?59/20?=2，可以看到符合所有冶炼记录。

当 V=25?时，有：?75/25?=3，?53/25?=2，?59/25?=2，可以看到符合所有冶炼记录。

求取公式

?c[i] = a[i] / b[i];? ?//计算最大值（取最小的那个）
?d[i] = a[i] / (b[i] + 1) + 1;? ?//计算最小值? （取最大的那个）

列如：

75/3=25，53/2=26，59/2=29? 取25，26，29，最小的那个即为最大值。

75/（3+1）+1=19，53/（2+1）+1=18，59/（2+1）+1=20 取19，18，20，最大的那个即为最小值。

如果出现部分样例不通过的现象，要注意?int a[100001], b[100001], c[100001], d[100001]; // 声明四个数组a、b、c、d，数组的取值范围。

运行截图