第十四届蓝桥杯 2023 C/C++组 冶炼金属

目次

标题：
标题描述：
标题链接：
思绪：
核心思绪：
思绪详解：
代码：
代码详解：

---

标题：

标题描述：

标题链接：

蓝桥云课 冶炼金属
洛谷 P9240 [蓝桥杯 2023 省 B] 冶炼金属
思绪：

核心思绪：

整数二分的两个模板
思绪详解：

由题求转换率V的最小值和最大值，结合题意不难发现存在单调性和二段性。见到同时求V的最小值和最大值，第一想法就是整数二分的两个模板。两次二分,一次求v的最小值,一次求v的最大值
代码：

代码详解：

1. #include<bits/stdc++.h> //自己做的时候第一思路就是整数二分的两个模板
2. using namespace std;    //两次二分,一次求v的最小值,一次求v的最大值
4. int a,b;
5. int n;
6. int vmin=-1;
7. int vmax=1e9;
9. int main()
10. {
11.         cin>>n;
12.         while(n--)  //n行输入数据
13.         {
14.                 int a,b;
15.                 scanf("%d %d",&a,&b);
16.                 int l1=1;  //由题1<=b<=a<=10^9,a/v=b,所以1<=v<=10^9,左右边界可以确定
17.                 int r1=1e9;
18.                 while(l1<r1)
19.                 {
20.                         int mid=l1+r1>>1; //先求满足每行数据v的最小值,这里用的第一个模板
21.                         if(a/mid<=b) //这里是模板的check(mid),mid>=v,由题a/v=b,所以a/mid<=b
22.                         {
23.                                 r1=mid;
24.                         }
25.                         else
26.                         {
27.                                 l1=mid+1;
28.                         }
29.                 }
30.                 if(l1>vmin)  //输入n行数据,即有n个l1,每次的l1都是满足该行数据的最小v,但是由题vmin要满足
31.                 {            //所有行的数据,所以vmin是l1里面的最大值
32.                         vmin=l1;
33.                 }
34.                 int l2=1;
35.                 int r2=1e9;
36.                 while(l2<r2)
37.                 {
38.                         int mid=l2+r2+1>>1; //再求满足每行数据v的最大值,这里用的第二个模板
39.                         if(a/mid>=b) //这里是模板的check(mid),mid<=v,由题a/v=b,所以a/mid>=b
40.                         {
41.                                 l2=mid;
42.                         }
43.                         else
44.                         {
45.                                 r2=mid-1; //记忆小技巧,如果这里有-1上面mid那里就补个+1
46.                         }
47.                 }
48.                 if(l2<vmax) //输入n行数据,即有n个l2,每次的l2都是满足该行数据的最大v,但是由题vmax要满足
49.                 {           //所有行的数据,所以vmax是l2里面的最小值
50.                         vmax=l2;
51.                 }
52.         }
53.         printf("%d %d",vmin,vmax);
54.         return 0;
55. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。