- Fdsama 的博客
二分答案
- 2024-1-21 18:54:36 @
Copyright by
引入
首先我们来做一个游戏
请在一个范围内取一个数x
询问者每次询问一个数,若x等于该数则结束
若x大于该数就说大
若x小于该数就说小
很简单的规则,让我们来看看怎么操作
法一:直接枚举,从1问到x
但是sei还这么做啊~
法二:每次问答案可能存在区间的一半位置,缩小答案范围,直到找到答案
这就是二分答案
模板
那么接下来我们用代码的方式实现上述操作
直接枚举:
#include<bits/stdc++.h>
using namespace std;
int main() {
int x;
cin >> x;
int cnt = 0;
int l = 1, r = 1000;
for (int i = l; i <= r; i++) {
cnt++;
if (i == x) {
cout << x << endl;
break;
}
}
cout << "Guess times:" << cnt << endl;
return 0;
}
二分答案:
#include<bits/stdc++.h>
using namespace std;
int main() {
int x;
cin >> x;
int cnt = 0;
int l = 1, r = 1000;
while (l < r) {
cnt++;
int mid = (l + r) / 2;
cout << endl;
cout << "range:" << l << "~" << r << endl;
cout << "mid value:" << mid << endl;
if (x <= mid) {
r = mid;
cout << "Left" << endl;
} else {
l = mid + 1;
cout << "Right" << endl;
}
}
cout << l << endl;
cout << "Guess times:" << cnt << endl;
return 0;
}
那么这样就能大幅度减少求出答案所需的时间
二分答案,首先需要确定答案的范围
其次,要判定一个数与答案的大小关系
最后,要确定输出的答案是什么
int l = 1, r = 1000;
while (l < r) {
int mid = (l + r) >> 1;
//这里要用>>,为了处理负数情况
//如果Check(mid)返回true,说明答案<=mid
if (Check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
如上,只要实现Check函数就可以了
模板题
例2
#include<bits/stdc++.h>
using namespace std;
int n, K;
int a[10010];
bool Check(int L) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i] / L;
}
return sum >= K;
}
int main() {
cin >> n >> K;
int mx = 0;
for (int i = 1; i <= n; i++) {
double d;
cin >> d;
a[i] = 100 * d;
mx = max(mx, a[i]);
}
int l = 0, r = mx;
while (l < r) {
int mid = ((l + r) >> 1) + 1;
if (Check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
int ans = l;
if (ans < 1) {
printf("0.00");
} else printf("%.2f", ans / 100.0);
return 0;
}
例3
如果在题目中看到了最大的最小或最小的最大这样的字眼,就可以考虑二分答案
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[100010];
bool Check(int x) {
int money = 0, month = 1;
for (int i = 1; i <= n; i++) {
if (money + a[i] > x) {
money = a[i];
month++;
} else {
money += a[i];
}
}
return month <= m;
}
int main() {
int sum = 0;
int mx = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
mx = max(mx, a[i]);
}
int l = mx, r = sum;
while (l < r) {
int mid = (l + r) >> 1;
if (Check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
cout << l << endl;
return 0;
}