愿尔安然无恙


私信TA

用户名:H2130819045

访问量:10413

签 名:

向往星辰大海,喜欢落日晚风。

等  级
排  名 59
经  验 10244
参赛次数 16
文章发表 55
年  龄 20
在职情况 学生
学  校 贺州学院
专  业 软件工程

  自我简介:

不想改bug ^_^

TA的其他文章

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

话不多说,先上图(题目样例分析如下)

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;
 }


 

0.0分

62 人评分

  评论区

太牛了
2024-03-27 21:21:25
#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;
}为什么错了啊
2024-03-26 19:37:55
#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;
}为什么错了呀呜呜呜
2024-03-19 15:28:34
额 就是想问一下为什么一定要设置flag 不可以一开始就直接赋初始值然后去比较吗
2024-03-19 15:01:47
额 就是想问一下为什么一定要设置flag 不可以一开始就直接赋初始值然后去比较吗
2024-03-19 15:01:32
牛哇牛哇
2023-11-25 16:12:43
6666
2023-09-17 21:05:10
  • «
  • 1
  • »