二分是基础算法之一,常用于答案有单调性的题目,或者穷举会超时的题目
int search(int l, int r) {
while (l + 1 < r) {
int mid = l + (r - l) >> 1; // 防溢出
if (check(mid)) l = mid; else r = mid;
}
return l;
}
例题
洛谷 - P2440 经典二分例题
code
// URL: https://www.luogu.com.cn/problem/P2440
// Memory Limit: 128 MB
// Time Limit: 1000 ms
#include <bits/stdc++.h>
using namespace std;
#define debug(args...) fprintf(stderr, ##args)
#define int ll
using ll = long long;
using ull = unsigned long long;
const int inf = 0x3f3f3f3f;
const int mod = 998244353; // 998244383, 1e9 + 7
const double eps = 1e-6;
const int N = 1e5 + 7;
const int M = 2e6 + 7;
namespace ckb2008 {
int n, k, l, r = inf, a[N];
bool check(int x) {
int y = 0;
for (int i = 1; i <= n; ++i) y += a[i] / x;
return y >= k;
}
signed main() {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid;
else r = mid;
}
printf("%d", l);
return 0;
}
}
signed main() { return ckb2008::main(); }