#C++3150——蓝桥杯2023年第十四届省赛真题-冶炼金属(分块)

**********************************************************************************************************************

话不多说，先上图（题目样例分析如下）

当时比赛时的思路是，找出最大下限+1，最小上限（这里分别用Min+1,Max来表示）

对于每一次输入的普通金属数量(a)与特殊金属数量(b)

通过观察a，b与最终结果的关系

我们可以发现 a/b 是在满足题意的情况下，冶炼单位特殊金属所使用的最大普通金属数量，我们称为“可以触碰的冶炼上限”

（再大普通金属就不够用了）^_^

同样的，也能看出 a/(b+1) 是刚好冶炼多一个特殊金属时，单位特殊金属所使用的最小普通金属数量，与之相反我们称为“不能触碰的冶炼下限“

（再小（包括等于）特殊金属就会变多），不能取到，只能往大一个单位，这也是我们为什么最终Min+1的原因！！！

以下为样例分析过后得到的边界范围，以及相交情况

理解完以上过后，就到了代码实现环节。

因为我们要取最大交集（所有数据都满足的情况），所以我们只需要用Min和Max来维护下限的最大值（输出结果记得+1）、上限的最小值，就可得出最终答案

这是一种对数据进行分块处理的思想，此题二分查找好像也是可以通过的，大家可以自己动手试一试

AC代码:

#include <iostream> 
using namespace std;
int main()
{
    int m,a,b,Min,Max,flags=0;//flags标记是否为第一次输入
    cin>>m;
    while(m--)//表示输入m组数据
    {
        cin>>a>>b;//输入普通金属、特殊金属数量
        if(a/b<Max&&flags==1)//维护上限最小值
        {
            Max=a/b;
        }
        if(a/(b+1)>Min&&flags==1)//维护下限最大值
        {
            Min=a/(b+1);
        }
        if(flags==0)//让第一次输入的数据作为大小判断的成员，这样就不用考虑Max、Min的初始值
        {
            Max=a/b;
            Min=a/(b+1); 
            flags=1;//标记已经初始化
        }
     } 
     cout<<Min+1<<" "<<Max;//因为下线不能触碰，得加1
    return 0;
 }