二分查找 ``` #include<bits/stdc++.h> #include<algorithm> #include<vector> using namespace std; const int MAX_N = 1e4 + 1; int N, A[MAX_N], B[MAX_N]; bool check_min(int V) { for(int i = 1;i <= N;++i) { if(A[i] / V > B[i]) { return false; } } return true; } bool check_max(int V) { for(int i = 1;i <= N;++i) { if(A[i] / V < B[i]) { return false; } } return true; } int main() { ios::sync_with_stdio(0);cin.tie(0); cin>>N; for(int i = 1;i <= N ;++i) { cin>> A[i] >> B[i]; } int L = 1,R = 1000000000,V_min;//先找最小值 while(L <= R) { int mid = L + R >> 1; if(check_min(mid))//如果复符合要求 { V_min = mid; R = mid - 1; } else { L = mid + 1; } } L = 1, R = 1000000000; int V_max; while(L <= R) { int mid = L + R >> 1; if(check_max(mid)) { V_max = mid; L = mid + 1; } else { R = mid - 1; } } cout<<V_min<<" "<<V_max<<endl; return 0; } ```

代码很简单，不加注释了 ``` #include<bits/stdc++.h> using namespace std; int c[10000]; int d[10000]; int main() { int n;cin >> n; for(int i = 0;i < n; ++ i) { int a, b;cin >> a >> b; c[i] = a / b; d[i] = a / (b + 1); } sort(c, c + n); sort(d, d + n); cout << d[n - 1] + 1 << ' '; cout << c[0]; return 0; } ```

``` #include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e4 + 10; int a[N], b[N]; int n; bool check1(int u) { for(int i = 0; i < n; i ++ ) { if(a[i] / u > b[i]) return 0; } return 1; } bool check2(int u) { for(int i = 0; i < n; i ++ ) { if(a[i] / u < b[i]) return 0; } return 1; } signed main() { cin >> n; for(int i = 0; i < n; i ++ ) cin >> a[i] >> b[i]; int l = 0, r = 1e9; while(l < r) { int mid = (l + r) >> 1; if(check1(mid)) r = mid; else l = mid + 1; } cout << l << " "; r = 1e9; while(l < r) { int mid = (l + r + 1) >> 1; if(check2(mid)) l = mid; else r = mid - 1; } cout << l; } ```

` ``` #include<bits/stdc++.h> using namespace std; int n,a,b; int minn=0,maxn=1e9; int main(){ cin>>n; while(n--) { cin>>a>>b; minn=max(minn,(int)floor(a/(b+1))+1); maxn=min(maxn,(int)floor(a/b)); ``` ``` } cout<<minn<<" "<<maxn<<endl; ``` ``` return 0； ``` } `

``` #include<iostream> using namespace std; int main(){ int N = 0; while(~scanf("%d",&N)){ int A[N]; int B[N]; for(int i = 0;i < N;i++){ cin >> A[i] >> B[i]; } int min = 10000; int max =0; for(int i = 1;i < A[0];i++){ int re = 0; for(int j = 0;j < N;j++){ if(A[j]/i == B[j]){ re++; } else break; } if(re == N){ if(max < i){ max = i; } if(min > i){ min = i; } } } cout << min << " " << max<<endl; } return 0; } ```

``` #include<bits/stdc++.h> using namespace std; long long A,B,Vmax=1e9,Vmin=0; int main() { int N; cin >> N; for(int i=1;i<=N;i++) { cin >>A>>B; Vmax=std:min(Vmax,A/B); Vmin=max(Vmin,A/(B+1)+1); } cout << Vmin<<" "<<Vmax; } ``` ```

``` //因为 O / V = X , V = O / X , O / (X+1) + 1 < V <= O / X; #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; int max_ = 2e9 , min_ = 0; while(n--){ int o,x; cin >> o >> x; int l = o / (x + 1) + 1 , r = o / x; //带入公式左边界和右边界 max_ = min(max_ , r); min_ = max(min_ , l); } cout << min_ << " " << max_; return 0; } ```

``` #include <bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int n, a[N], b[N]; int max_; bool check(int mid) { for (int i = 0; i < n; i ++) { if (b[i] != a[i] / mid) return false; } return true; } int binary_search_min(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return r; } int binary_search_max(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) { l = mid + 1; } else { r = mid; } } return r; } int main(void) { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n; for (int i = 0; i < n; i ++) cin >> a[i] >> b[i]; max_ = a[0] / b[0]; for (int i = 0; i < n; i ++) max_ = min(max_, a[i] / b[i]); int ans_min = binary_search_min(1, max_); cout << ans_min << ' ' << binary_search_max(ans_min, max_) << '\n'; } ```

import java.util.Arrays; import java.util.Scanner; //https://dashoj.com/d/lqbproblem/p/1 public class Main{ ``` public static void main(String []args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int [][]arr=new int[n][2]; for(int i=0;i<n;i++) { arr[i][0]=scanner.nextInt(); arr[i][1]=scanner.nextInt(); } //记录最大值和最小值 long [][]val=new long[n][2]; //把每个记录的最大值和最小值存在数组中 for(int i=0;i<n;i++) { //最小值 val[i][0]=arr[i][0]/(arr[i][1]+1)+1; //最大值 val[i][1]=arr[i][0]/(arr[i][1]); } long v1=0; long v2=Integer.MAX_VALUE; for(int k=0;k<n;k++) { if(v1<val[k][0]) { v1=val[k][0]; } if(v2>val[k][1]) { v2=val[k][1]; } } System.out.print(v1+" "+v2); } ``` }

import os import sys 请在此输入您的代码 n = int(input()) a = [0]n b = [0]n for i in range(n): a[i],b[i] = map(int,input().split()) ans = [] flag = 1 for i in range(1,100000000): for j in range(n): if a[j]//i != b[j]: flag = 0 break if flag: ans.append(i) break flag = 1 flag = 1 for i in range(100000000,1,-1): for j in range(n): if a[j]//i != b[j]: flag=0 break if flag: ans.append(i) break flag = 1 print(ans)