題目如下:
拿到題我們來看一下,題目的意思,就是求出N個記錄中的最大最小值,言外之意就是,如果超過了這個最大值不行,如果小于這個最小值也不行,所以我們得出,這道題是一個二分答案的題目,求出分界點。
首先我們輸入 N 個組別,分別輸入a , b 。
我們先討論最小值,我們寫一個binary_min
函數,用來二分答案的最小值,記最小值為 ans
首先,左邊界為 1
通過題目我們知道 我們要求的 V在分母上
所以我們最小為1
,最大則為當前a(分子)
的值
下來我們開始二分,在二分答案中我們應該寫成while(l<r)
這樣我們就不用記錄中間的狀態了(下面注釋中會說到), mid=l+r>>1
取中值,下來進入主要邏輯,當a/mid(V)<=b
的時候,我們可以得出我們現在的值在分界點的左邊,需要將V
的值變大,那么就需要將分母上的值(mid)
變小,那么我們就需要向左收縮區間令r=mid(這里說明為什么應該為l<r,我們在之前的二分中,左閉右開時,循環的條件為while(l<=r),而這次需要寫成l<r,我們最終要找的是臨界點 所以我們最后需要 l==r 而不是l=r+1)
當寫成while(l<=r)時,錯誤寫法
:
// 錯誤示例:使用 l <= r 但不記錄答案
int binary_min(int a, int b) {int l = 1, r = a;while (l <= r) { // 問題1:循環會在 l=r+1 時結束int mid = (l + r) / 2;if (a / mid <= b) {r = mid - 1; // 問題2:可能錯過正確答案} else {l = mid + 1;}}return l; // 錯誤:循環結束時 l 可能已超出有效范圍
}
最主要的就是可能會直接跳過最佳的答案,導致答案不正確(采用左閉右閉的寫法時,應該確保每次右邊的邊界都不會被跳過,由于我們的循環條件為l<r)所以我們應該記錄一下右邊界的值
所以應該向右收縮時記錄值
if (a / mid <= b) {ans = mid; // 記錄當前有效解r = mid - 1; // 向左收縮(關鍵:r=mid-1而非r=mid)} else {l = mid + 1;}
正確寫法
int binary_min(int a, int b) {int l = 1, r = a;while (l < r) {int mid = (l + r) >> 1;if (a / mid <= b) {r = mid; // 保留當前 mid 作為候選} else {l = mid + 1;}}return l; // 循環結束時 l 即為答案
}
了解了這一原理,下來繼續寫題,我們寫完函數之后試著輸出一下。
得到了這樣一組數據,為什么會出現這種呢?因為有三個記錄,每個記錄對應著一個最小值,對于每個 (a, b),滿足條件的 V 可能形成一個區間 [min_V, max_V]。當有多組輸入時,我們需要找到一個公共的 V 范圍,使得所有組的條件都被滿足。
代碼
ans=max(ans,binary_min(a,b));ans2=min(ans2,binary_max(a,b));
我們每次都會獲得一個V
我們要在所有的可能最小值里面選出一個最大的,在所有可能得最大值中選擇一個最小的,以此來滿足公共區間例如在上面的例子中,18已經是最小的值了,所以我們答案可以大于等于18,所以我們需要取這一堆數的最大值,同理
獲得了每組數據的最大上限,大的不一定全部滿足,小的一定全部滿足,找到其中的最小值,就是我們最終答案的最大值
AC代碼:
#include <iostream>
#include<limits.h>
#include<algorithm>
using namespace std;
//找最大值
int binary_max(int a,int b){int l=1,r=a;while(l<r){int mid=(l+r+1)>>1;if((a/mid)>=b){l=mid;}elser=mid-1;}return l;
}//找最小值
int binary_min(int a,int b){int l=1,r=a;while(l<r){int mid=(l+r)>>1;if((a/mid)<=b){r=mid;}elsel=mid+1;}return l;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int N;cin>>N;int ans=INT_MIN,ans2=INT_MAX;while(N--){int a,b;cin>>a>>b;ans=max(ans,binary_min(a,b));ans2=min(ans2,binary_max(a,b));}cout<<ans<<" "<<ans2;return 0;
}