石家庄营销网站建设,对网站域名销户怎么做,平板网站建设,微信api接口对于这个题#xff0c;V越大#xff0c;除出来的数就越小#xff0c;V越小#xff0c;除出来的数就越大#xff0c;当我们找一个最大和最小值的时候#xff0c;就可以通过这个性质进行二分来求解。
可以通过求满足 [ A V ] [\frac{A}{V}] [VA] 小于等于 B B B的最小的…对于这个题V越大除出来的数就越小V越小除出来的数就越大当我们找一个最大和最小值的时候就可以通过这个性质进行二分来求解。
可以通过求满足 [ A V ] [\frac{A}{V}] [VA] 小于等于 B B B的最小的 V V V来求最小值通过满足 [ A V ] [\frac{A}{V}] [VA] 小于等于 B − 1 B-1 B−1的 V V V最小的值来求最大值这里是根据下取整函数的性质来决定的取整函数的函数图像是一段段的横线可以观察得B的V的最大值就是B-1的V的最小值。
代码1
#includeiostream
#includecstring
#includealgorithm
using namespace std;int get(int a, int b) {//二分函数//b最小取1但是下面调用函数时有b-1所以b有可能取到0那么r就要取到比1e9大//则定义r为1e91int l 1, r 1e9 1;while (l r) {int mid l r 1;if (a / mid b)r mid;else l mid 1;}return r;
}int main() {int n; cin n;//最小一定是1最大只能取1e9大于1e9时B会得到0不满足题目条件int minV 1, maxV 1e9;while (n--) {int a, b; cin a b;minV max(minV, get(a,b));maxV min(maxV, get(a, b - 1) - 1);}cout minV maxV;return 0;
}另一种二分法 当我们要求V的最小值的时候先浮现出一个数轴
|----------------------|----------------------|
L mid R因为这里是找数所以不是之前的那些需要满足条件这里只需要看大小关系。 如果 [ A m i d ] [\frac{A}{mid}] [midA]大于B就说明mid取小了所以就要往右边找也就是从mid 1 ~ R找如果小于B那就要从L ~ mid找。
对于求最大值也是同理。
另一种代码非常模板风味的二分代码
#includeiostream
#includealgorithm
using namespace std;
const int N 1e4 10;int n;
int a[N], b[N];bool check1(int mid) { //check1求最小值用for (int i 0; i n; i) {if (a[i] / mid b[i])return false; }return true;
}bool check2(int mid) { //check2求最大值用for (int i 0; i n; i) {if (a[i] / mid b[i])return false;}return true;
}int main() {cin n;for (int i 0; i n; i) cin a[i] b[i];//求最小值int l 1, r 1e9;while (l r) {int mid l r 1;if (check1(mid))r mid;else l mid 1;}cout r ;//求最大值l 1, r 1e9;while (l r) {int mid l r 1 1;if (check2(mid)) l mid;else r mid - 1;}cout r endl;return 0;
}由于是复习二分故不记录数学做法
