C: 冶炼金属(10分)
问题描述
小蓝有一个神奇的炉子用于将普通金属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
对于100%的评测用例,1≤N≤1e4,1≤B≤A≤1e9。
我的代码:
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n;
int a;
int b;
int l;
int r;
int min = 0;
int max = 0x3f3f3f3f;
cin >> n;
while (n--) {
cin >> a >> b;
r = 1.0 * a / b;//最大V
l = 1.0 * a / (b + 1);//大于最小V
if (min < l) {
min = l;
}
if (max > r) {
max = r;
}
}
cout << min <<" "<< max << endl;
return 0;
}
这个程序是错误的。
原因:浮点型转换为整型时,小数部分被直接舍弃,并不会遵循四舍五入的原则。
因此预期结果为:20,25;可实际结果为:19,25
如何让最小值有小数部分时直接进一位呢?
标准代码:
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int ansMin = 0, ansMax = 1e9;
while (n--) {
int a, b;
cin >> a >> b;
ansMin = max(a / (b + 1) + 1, ansMin);
ansMax = min(a / b, ansMax);
}
cout << ansMin << " " << ansMax << endl;
return 0;
}
可以看到,这里直接让最小值+1,避免了最小值出现了1的偏差。
C++的<algorithm>库中有max函数,可以返回两个数中的较大值。