1. 首页
  2. 题解列表
  3. 3150题题解

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

8450 阅读 14 评论
原题链接：蓝桥杯2023年第十四届省赛真题-冶炼金属

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

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

QQ图片20230413131319.png

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

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

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

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

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

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

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

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

QQ图片20230413132909.png

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

因为我们要取最大交集（所有数据都满足的情况），所以我们只需要用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;
 }


点赞(1)
　

0.0分

51 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
点进来你会后悔的
点进来你会后悔的
简简单单的循环
简简单单的循环
简单的回文数
简单的回文数

评论列表 共有 14 条评论

uq_84721880743 10月前 回复TA 
#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a,b;
    scanf("%d %d",&a,&b);
    int max,min;
        min=a/(b+1);
        max=a/b;
    for(int i=0;i<n;i++){
        scanf("%d %d",&a,&b);
        if(min<(a/(b+1))){
            min=a/(b+1);
        }
        if(max>a/b){
            max=a/b;
        }
    }
    printf("%d %d",min+1,max);
},楼主真的是高手，看来你的讲解茅塞顿开，真感觉自己像一个dinner，呜呜呜
蓝桥便便羊 11月前 回复TA 
太牛了
愿尔安然无恙 11月前 回复TA 
@想吃灌汤烤冷面 这是修改过后的
愿尔安然无恙 11月前 回复TA 
@想吃灌汤烤冷面 #include <iostream> using namespace std; int main() { 	int n; 	int a=0,b=0; 	int min[1001],max[1001]; 	int in=10000001,ax=0; 	scanf("%d",&n); 	for(int i=0;i<n;i++) 	{ 		cin>>a>>b; 		 		min[i]=a/(b+1)+1; 		max[i]=a/b; 		if(min[i] > ax) 		{ 			ax = min[i]; 		} 		if(max[i] < in) 		{ 			in = max[i]; 		} 	} 	cout<<ax<<" "<<in; 	return 0; }
愿尔安然无恙 11月前 回复TA 
@想吃灌汤烤冷面 你的初始最大值不够，极端数据下是通过不了的。
想吃灌汤烤冷面 11月前 回复TA 
#include <iostream>
using namespace std;
int main()
{
	int n;
	int a=0,b=0;
	int min[101],max[101];
	int in=10000,ax=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		cin>>a>>b;
		
		min[i]=a/(b+1)+1;
		max[i]=a/b;
		if(min[i] > ax)
		{
			ax = min[i];
		}
		if(max[i] < in)
		{
			in = max[i];
		}
	}
	cout<<ax<<" "<<in;
	return 0;
}为什么错了啊
愿尔安然无恙 11月前 回复TA 
@听 也就是你的初始值有问题，我加flag的目的就是为了避免设置初始值。
愿尔安然无恙 11月前 回复TA 
@听 最小值不一定是0，一般会比0大，所以你可以给min一个比较大的值，max一个比较小的值。
愿尔安然无恙 11月前 回复TA 
@听 可以不用设置，但是这样你就需要给Max和Min一个初始值，我没有去确定边界的大小，所以直接用输入数据构造。
听 11月前 回复TA 
#include <iostream>

using namespace std;

int main()
{
    int N, A, B, max, min = 0;
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> A >> B;
        max = A / B;
        min = A / (B + 1);
        if(A / B < max)
        {
            max = A / B;
        }
        if(A / (B+1) > min)
        {
            min = A / (B+1);
        }
        cout << min + 1 << max << endl;
    }
    
    return 0;
}
            max=A/B;
        }
        if(A/(B+1)>min)
        {
            min=A/(B+1);
        }
        cout<<min+1<<max<<endl;
    }
    return 0;
}为什么错了呀呜呜呜