目錄
題目：
題目描述：
題目鏈接：
思路：
核心思路：
思路詳解：
代碼：
代碼詳解：
題目：
題目描述：
題目鏈接：
藍橋云課 冶煉金屬
洛谷 P9240 [藍橋杯 2023 省 B] 冶煉金屬
思路：
核心思路：
整數二分的兩個模板
思路詳解：
由題求轉換率V的最小值和最大值，結合題意不難發現存在單調性和二段性。見到同時求V的最小值和最大值，第一想法就是整數二分的兩個模板。兩次二分,一次求v的最小值,一次求v的最大值
代碼：
代碼詳解：
#include<bits/stdc++.h> //自己做的時候第一思路就是整數二分的兩個模板
using namespace std; //兩次二分,一次求v的最小值,一次求v的最大值 int a,b;
int n;
int vmin=-1;
int vmax=1e9;int main()
{cin>>n;while(n--) //n行輸入數據 {int a,b;scanf("%d %d",&a,&b);int l1=1; //由題1<=b<=a<=10^9,a/v=b,所以1<=v<=10^9,左右邊界可以確定 int r1=1e9;while(l1<r1){int mid=l1+r1>>1; //先求滿足每行數據v的最小值,這里用的第一個模板 if(a/mid<=b) //這里是模板的check(mid),mid>=v,由題a/v=b,所以a/mid<=b {r1=mid;}else{l1=mid+1;}}if(l1>vmin) //輸入n行數據,即有n個l1,每次的l1都是滿足該行數據的最小v,但是由題vmin要滿足 { //所有行的數據,所以vmin是l1里面的最大值 vmin=l1;}int l2=1;int r2=1e9;while(l2<r2){int mid=l2+r2+1>>1; //再求滿足每行數據v的最大值,這里用的第二個模板 if(a/mid>=b) //這里是模板的check(mid),mid<=v,由題a/v=b,所以a/mid>=b {l2=mid;}else{r2=mid-1; //記憶小技巧,如果這里有-1上面mid那里就補個+1 }}if(l2<vmax) //輸入n行數據,即有n個l2,每次的l2都是滿足該行數據的最大v,但是由題vmax要滿足 { //所有行的數據,所以vmax是l2里面的最小值 vmax=l2;}}printf("%d %d",vmin,vmax);return 0;
}
)
