g423 - Error
題目描述
題目要求找到一個最大的整數 v，使得將所有 a[i] 除以 v 後，得到的整數和至少為 2 * m。
解題思路
這題可以使用二分搜尋法來解決。二分搜尋的範圍是從 0 到 1e9。對於每個中間值 mid，我們計算將所有 a[i] 除以 mid 後的整數和。如果這個和大於等於 2 * m，則表示 mid 可能是一個解，我們繼續在 mid + 1 到 r 的範圍內搜尋更大的解。否則，表示 mid 太大，我們在 l 到 mid - 1 的範圍內搜尋更小的解。最終，二分搜尋會找到最大的滿足條件的 v。
複雜度分析
- 時間複雜度: O(n log(1e9))，其中 n 是
a陣列的長度。二分搜尋的次數是 log(1e9)，每次二分搜尋需要遍歷a陣列一次，時間複雜度為 O(n)。 - 空間複雜度: O(1)，因為我們只使用了常數級別的額外空間。
程式碼
#include <iostream>
using namespace std;
long long n,m,a[100005];
bool judge(long long v){
int ct=0;
for(int i=0;i<n;++i){
ct+=a[i]/v;
if(ct>=m)return 1;
}
return 0;
}
long long bs(long long l,long long r){
if(l>r)return r;
long long mid=(l+r)/2;
if(judge(mid)){
return bs(mid+1,r);
}
else{
return bs(l,mid-1);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m;
m*=2;
for(int i=0;i<n;++i)
cin >> a[i];
cout << bs(0,1e9);
}