常用的算法二分模板
1. 在数组a[]中找大于等于x的第一个数的下标
//int ans = lower_bound(a, a + n, x) - a
//相当于下方
int l = 0, r = n - 1;
while(l < r) {
int mid = l + r >> 1;
if(a[mid] >= x) r = mid;
else l = mid + 1;
}
cout << r;
2. 在数组a[]中找大于x的第一个数的下标
//int ans = upper_bound(a, a + n, x) - a
//相当于下方
int l = 0, r = n - 1;
while(l < r) {
int mid = l + r + 1 >> 1;
if(a[mid] <= x) l = mid;
else r = mid + 1;
}
cout << r;
例题
503.借教室
题目
思路
代码
//根据题意：有单调性，区间操作 二分+差分
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int r[N], d[N], s[N], t[N];
LL b[N]; //差分数组
int n, m;
bool check(int mid) {
for(int i = 1; i <= n; i++)
b[i] = r[i] - r[i - 1]; //初始化差分数组
for(int i = 1; i <= mid; i++) {
b[s[i]] -= d[i];
b[t[i] + 1] += d[i];
}
for(int i = 1; i <= n; i++ ) {
b[i] += b[i - 1];
if(b[i] < 0) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &r[i]);
for(int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);
int l = 1, r = m;
if(!check(m)) {
puts("0");
return 0;
}
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("-1\n%d", r);
return 0;
}
5407.管道
题目
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int n, len;
int l[N], s[N];
pair<int, int> q[N];
bool check(LL mid) { //mid为当前时间
int cnt = 0;
for(int i = 1; i <= n; i++) {
if(s[i] <= mid) {
// q[cnt++] = {mid - s[i], mid + s[i]}; 别忘了区间长度限制
int d = mid - s[i];
LL L = max(1, l[i] - d), R = min((LL)len, (LL)l[i] + d);
q[cnt++] = {L, R};
}
}
sort(q, q + cnt);
int st = -1, ed = -1;
for(int i = 0; i < cnt; i++) {
//这里是 ed+1 因为需要的是每个节点有水，相当于“相连”
if(q[i].first <= ed + 1) ed = max(ed, q[i].second);
else {
st = q[i].first, ed = q[i].second;
}
}
return st == 1 && ed == len;
}
int main() {
scanf("%d%d", &n, &len);
for(int i = 1; i <= n; i++)
scanf("%d%d", &l[i], &s[i]);
LL l = 0, r = 2e9; //最坏情况是2e9
while(l < r) {
LL mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << r;
return 0;
}
（多路合并）
1262.鱼塘钓鱼
思路
枚举最后一次钓鱼的鱼塘， 传入参数（第k个鱼塘， 钓鱼时间）
代码如下
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int T, n;
int s[N], d[N], t[N], spend[N];
int get_fish(int k) { //在第k个鱼塘当前能钓鱼数量
return max(0, s[k] - spend[k] * d[k]);
}
int work(int n, int T) {
int res = 0;
memset(spend, 0, sizeof spend);
for(int i = 0; i < T; i++) { //一共枚举T次，T分钟则可选择钓T次
int t = 1; //循环判断哪个鱼塘当前能钓鱼数最多
for(int j = 2; j <= n; j++)
if(get_fish(j) > get_fish(t))
t = j;
res += get_fish(t); //答案加上此时钓鱼数量
spend[t]++; //当前鱼塘钓鱼时间++
}
return res;
}
int main () {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
for(int i = 1; i <= n; i++) scanf("%d", &d[i]);
//走到第一个鱼塘不用时间
for(int i = 2; i <= n; i++) cin >> t[i], t[i] += t[i - 1];
cin >> T;
int res = 0;
// 枚举最后走到哪个鱼塘
for(int i = 1; i <= n; i++)
res = max(res, work(i, T - t[i])); //最后走到第i个鱼塘，钓鱼时间为T-t[i]
cout << res;
return 0;
}
4656.技能升级
题目：
思路分析：
代码和注释具体如下
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N], b[N];
bool check(int mid) {
LL res = 0;
for(int i = 0; i < n; i++)
if(a[i] >= mid)
res += (a[i] - mid) / b[i] + 1; //对于第i个技能所加的次数 ：差值 / 公差 + 1，因为差值为0时，还需要加一次
if(res >= m) return true; //判断对于最后一次为mid值所对应加技能的总次数是否满足要求m次
return false;
}
int main() {
scanf("%d%d", &n, &m);
//m 的范围太大， 故从n下手，也就是枚举加的技能点值，二分答案
for(int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]);
int l = 0, r = 1e6; //左右边界（最后一次(m)加的技能点）
while(l < r) {
// l 和 r 的更新，***关键***
//这里的话由于所加技能点是从大到小排序进行选择的，故答案必然是[mid,...]的区间（mid对应的值可能不止一个），而小于mid的不符合
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
LL res = 0, cnt = 0; //次数，答案
for(int i = 0; i < n; i++) {
if(a[i] > r) { // r 即为最后一次加的技能点数
int s = (a[i] - r) / b[i] + 1; //第i个技能所加次数
int an = a[i] - (s - 1) * b[i]; //最后一次升级的点数
res += (LL)(a[i] + an) * s / 2; //等差数列公式求出所加技能点和
cnt += s; //累加加技能次数
}
}
LL ans = res - (cnt - m) * r; //最后一个数值可能加的次数不止一次，故需要特殊处理
cout << ans;
return 0;
}
