原题单链接：二分训练
AcWing 789 数的范围
输入非递减数组，输出目标值首次和最后出现的下标（从 0 开始）。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,q; cin >> n >> q; vector<int> a(n);
for(auto &x:a) cin >> x;
while(q--) {
int x; cin >> x;
int l=lower_bound(a.begin(),a.end(),x)-a.begin();
int r=upper_bound(a.begin(),a.end(),x)-a.begin()-1;
if(l==n || a[l]!=x) cout << "-1 -1\n";
else cout << l << ' ' << r << '\n';
}
}
浮点二分：三次方根
适用于输入在 [-1000000,1000000] 内的实数。
#include <bits/stdc++.h>
using namespace std;
int main() {
double n; cin >> n; double l=-100,r=100;
for(int i=0;i<100;++i) { double mid=(l+r)/2; if(mid*mid*mid<n) l=mid; else r=mid; }
cout << fixed << setprecision(6) << (l+r)/2 << '\n';
}
有序数组中首次出现的位置
输入非递减数组，按从 1 开始的下标输出；不存在则输出 -1。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m; cin >> n >> m; vector<int> a(n); for(auto &x:a) cin >> x;
while(m--) { int x; cin >> x; auto it=lower_bound(a.begin(),a.end(),x);
cout << (it!=a.end() && *it==x ? int(it-a.begin())+1 : -1) << ' '; }
}
A-B 数对
统计满足 A-B=C 的有序下标对，适用于 C>0。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; long long c; cin >> n >> c; vector<long long> a(n); for(auto &x:a) cin >> x;
sort(a.begin(),a.end()); long long ans=0;
for(auto b:a) ans+=upper_bound(a.begin(),a.end(),b+c)-lower_bound(a.begin(),a.end(),b+c);
cout << ans << '\n';
}
砍树
二分最大可行高度；题目须保证木材总量足够。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; long long m; cin >> n >> m; vector<int> a(n); for(auto &x:a) cin >> x;
long long l=0,r=*max_element(a.begin(),a.end());
while(l<r) { long long mid=(l+r+1)/2,sum=0; for(auto x:a) sum+=max(0LL,x-mid);
if(sum>=m) l=mid; else r=mid-1; }
cout << l << '\n';
}
切绳子
输入整数绳长，求能切出至少 k 段的最大整数长度。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,k; cin >> n >> k; vector<int> a(n); for(auto &x:a) cin >> x;
int l=0,r=*max_element(a.begin(),a.end());
while(l<r) { int mid=l+(r-l+1)/2; long long cnt=0; for(auto x:a) cnt+=x/mid;
if(cnt>=k) l=mid; else r=mid-1; }
cout << l << '\n';
}
跳石头
#include <bits/stdc++.h>
using namespace std;
int main() {
int L,n,m; cin >> L >> n >> m; vector<int> a(n+2); for(int i=1;i<=n;++i) cin >> a[i];
sort(a.begin()+1,a.begin()+n+1); a[n+1]=L;
int l=0,r=L;
while(l<r) { int mid=l+(r-l+1)/2,last=0,cnt=0;
for(int i=1;i<=n+1;++i) { if(a[i]-a[last]<mid) ++cnt; else last=i; }
if(cnt<=m) l=mid; else r=mid-1;
}
cout << l << '\n';
}
路标设置
二分最小的最大间距；每个长度 d 的间隔需增加 (d-1)/mid 个路标。
#include <bits/stdc++.h>
using namespace std;
int main() {
int L,n,k; cin >> L >> n >> k; vector<int> a(n); for(auto &x:a) cin >> x;
a.push_back(0); a.push_back(L); sort(a.begin(),a.end());
int l=1,r=max(1,L);
while(l<r) { int mid=(l+r)/2; long long cnt=0;
for(int i=1;i<(int)a.size();++i) { int d=a[i]-a[i-1]; if(d>0) cnt+=(d-1)/mid; }
if(cnt<=k) r=mid; else l=mid+1;
}
cout << l << '\n';
}