**********************************************************************************************************************
话不多说,先上图(题目样例分析如下)
当时比赛时的思路是,找出最大下限+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; }
0.0分
62 人评分
#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-27 10:25:15 |
你的初始最大值不够,极端数据下是通过不了的。
愿尔安然无恙 2024-03-27 10:26:03 |
#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; }
愿尔安然无恙 2024-03-27 10:26:35 |
这是修改过后的
#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; }为什么错了呀呜呜呜
额 就是想问一下为什么一定要设置flag 不可以一开始就直接赋初始值然后去比较吗
愿尔安然无恙 2024-03-24 19:40:29 |
可以不用设置,但是这样你就需要给Max和Min一个初始值,我没有去确定边界的大小,所以直接用输入数据构造。
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:742 |
不会做的浏览:869 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:698 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:992 |
printf基础练习2 (C语言代码)浏览:644 |
校门外的树 (C语言代码)浏览:692 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:773 |
模拟计算器 (C++代码)浏览:798 |
【偶数求和】 (C语言代码)浏览:430 |
简单的a+b (C语言代码)浏览:941 |