当前位置：首页 > news >正文

第十四届蓝桥杯_省赛B组(C).冶炼金属

news 2025/6/12 17:41:18

题目如下:

在这里插入图片描述
拿到题我们来看一下，题目的意思，就是求出N个记录中的最大最小值，言外之意就是，如果超过了这个最大值不行，如果小于这个最小值也不行，所以我们得出，这道题是一个二分答案的题目，求出分界点。
首先我们输入 N 个组别，分别输入a , b 。
我们先讨论最小值，我们写一个binary_min函数，用来二分答案的最小值，记最小值为 ans
首先，左边界为 1 通过题目我们知道我们要求的 V在分母上 所以我们最小为1，最大则为当前a(分子)的值
下来我们开始二分，在二分答案中我们应该写成while(l<r)这样我们就不用记录中间的状态了（下面注释中会说到）, mid=l+r>>1取中值,下来进入主要逻辑,当a/mid(V)<=b的时候，我们可以得出我们现在的值在分界点的左边，需要将V的值变大，那么就需要将分母上的值(mid)变小，那么我们就需要向左收缩区间令r=mid（这里说明为什么应该为l<r，我们在之前的二分中，左闭右开时，循环的条件为while(l<=r)，而这次需要写成l<r，我们最终要找的是临界点所以我们最后需要 l==r 而不是l=r+1）
当写成while(l<=r)时，错误写法：

// 错误示例：使用 l <= r 但不记录答案
int binary_min(int a, int b) {int l = 1, r = a;while (l <= r) {  // 问题1：循环会在 l=r+1 时结束int mid = (l + r) / 2;if (a / mid <= b) {r = mid - 1;  // 问题2：可能错过正确答案} else {l = mid + 1;}}return l;  // 错误：循环结束时 l 可能已超出有效范围
}

最主要的就是可能会直接跳过最佳的答案，导致答案不正确（采用左闭右闭的写法时，应该确保每次右边的边界都不会被跳过，由于我们的循环条件为l<r）所以我们应该记录一下右边界的值
所以应该向右收缩时记录值

		if (a / mid <= b) {ans = mid;  // 记录当前有效解r = mid - 1;  // 向左收缩（关键：r=mid-1而非r=mid）} else {l = mid + 1;}

正确写法

int binary_min(int a, int b) {int l = 1, r = a;while (l < r) {int mid = (l + r) >> 1;if (a / mid <= b) {r = mid;  // 保留当前 mid 作为候选} else {l = mid + 1;}}return l;  // 循环结束时 l 即为答案
}

了解了这一原理，下来继续写题，我们写完函数之后试着输出一下。
在这里插入图片描述
得到了这样一组数据,为什么会出现这种呢？因为有三个记录,每个记录对应着一个最小值，对于每个 (a, b)，满足条件的 V 可能形成一个区间 [min_V, max_V]。当有多组输入时，我们需要找到一个公共的 V 范围，使得所有组的条件都被满足。
代码

	ans=max(ans,binary_min(a,b));ans2=min(ans2,binary_max(a,b));

我们每次都会获得一个V我们要在所有的可能最小值里面选出一个最大的，在所有可能得最大值中选择一个最小的，以此来满足公共区间例如在上面的例子中，18已经是最小的值了，所以我们答案可以大于等于18,所以我们需要取这一堆数的最大值，同理
在这里插入图片描述
获得了每组数据的最大上限，大的不一定全部满足，小的一定全部满足，找到其中的最小值，就是我们最终答案的最大值

AC代码：

#include <iostream>
#include<limits.h>
#include<algorithm>
using namespace std;
//找最大值
int binary_max(int a,int b){int l=1,r=a;while(l<r){int mid=(l+r+1)>>1;if((a/mid)>=b){l=mid;}elser=mid-1;}return l;
}//找最小值
int binary_min(int a,int b){int l=1,r=a;while(l<r){int mid=(l+r)>>1;if((a/mid)<=b){r=mid;}elsel=mid+1;}return l;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int N;cin>>N;int ans=INT_MIN,ans2=INT_MAX;while(N--){int a,b;cin>>a>>b;ans=max(ans,binary_min(a,b));ans2=min(ans2,binary_max(a,b));}cout<<ans<<" "<<ans2;return 0;
}