二分法 + 数学公式
二分
发现 A/V 下取整是单调的, 只要单调就可以二分
#include<iostream>
using namespace std;
#include<algorithm>
// 找到A/V <= B 的V的最小值
int find_v(int a, int b) {
int l = 1, r = 1e9 + 1;
while (l < r) {
int mid = l + r >> 1;
if (a / mid <= b) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
int N;
scanf("%d", &N);
int v_min = 1, v_max = 1e9;
while (N--) {
int a, b;
scanf("%d%d", &a, &b);
v_min = max(v_min, find_v(a, b));
v_max = min(v_max, find_v(a, b - 1) - 1);
}
printf("%d %d", v_min, v_max);
return 0;
}
数学公式
把A/V的范围求出来 [B, B+1),然后用不等式求(有时候不要把题目想的太复杂,不一定要用算法)
#include<iostream>
using namespace std;
#include<algorithm>
int main(){
int n;
scanf("%d", &n);
int v_min=1, v_max = 1e9;
while(n--){
int a, b;
scanf("%d%d", &a, &b);
v_min = max(v_min, a/(b+1) + 1);
v_max = min(v_max, a/b);
}
printf("%d %d\n", v_min, v_max);
return 0;
}