本期主要讲解二分答案。
知识点
使用场景：
-
最小值最大化，或最大值最小化。
-
在限制条件下找最值。
与二分查找的区别：
L、R均为答案，而非下标。
输出：
- 最大化输出
L，反之输出R。
例题
T1
二分 \(M\) 的值，边界为 \(L=-1,R=\max{\{a_i\}}\)。每次枚举到一个 \(mid\) 就对于每个 \(a_i\)，计算能砍下的木头是否 \(\ge m\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,maxh,h[1000031];
bool check(int x){
int sum=0;
for(int i=1;i<=n;i++)
if(h[i]>x) sum+=h[i]-x;
return sum>=m;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>h[i],maxh=max(maxh,h[i]);
int l=-1,r=maxh+1;
while(l+1<r){
int mid=(l+r)>>1;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l;
return 0;
}
T2
二分 \(l\) 的值，边界为 \(L=0,R=\max{\{a_i\}}\)（注意 \(L\) 为 \(0\)，这样可以免去不必要的特判）。
每次枚举到一个 \(mid\)，则当前段数为 \(\sum^{n}_{i=1} \lfloor \dfrac{a_i}{mid} \rfloor\)，判断其是否 \(\ge m\) 即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,l[100031];
bool check(int x){
int sum=0;
for(int i=1;i<=n;i++) sum+=l[i]/x;
return sum>=k;
}
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>l[i];
int l=0,r=1e8+1;
while(l+1<r){
int mid=(l+r)>>1;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l;
return 0;
}
习题
T3
首先读入字符串，分离并计算出做一个汉堡需要的 \(B,S,C\)。记读入的已有材料数分别为 \(nb,ns,nc\)，需要的钱数分别为 \(mb,ms,mc\)，已有钱数为 \(money\)。
二分能做出的汉堡个数，边界为 \(L=-1,R=money+\max{(nb,ns,nc)}\)。对于每个 \(mid\)，计算出除去已有材料后还需要花的钱，与 \(money\) 作比较即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
string str;
int b,s,c;
int nb,ns,nc;
int mb,ms,mc;
int money;
bool check(int x){
int sum=0;
if(x*b>nb) sum+=(x*b-nb)*mb;
if(x*s>ns) sum+=(x*s-ns)*ms;
if(x*c>nc) sum+=(x*c-nc)*mc;
return sum<=money;
}
signed main(){
cin>>str;
cin>>nb>>ns>>nc;
cin>>mb>>ms>>mc;
cin>>money;
for(int i=0;str[i];i++){
if(str[i]=='B') b++;
else if(str[i]=='S') s++;
else c++;
}
int l=-1,r=money+max(nb,max(ns,nc))+1;
while(l+1<r){
int mid=(l+r)>>1;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l;
return 0;
}
T4
记需要 \(x\) 轮才能满足所有人的要求，且所有人共需要玩 \(s\) 轮游戏。
由定义可知 \(s=\sum^{n}_{i=1} a_i\)，并且由题意有 \((n-1)x \ge s\)。
则可以二分 \(x\) 的值，边界为 \(L=\max{\{a_i\}}-1,R=s+1\)。
每次枚举到一个 \(mid\)，就按照上式检查即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,s,m,a[100031];
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],s+=a[i],m=max(m,a[i]);
int l=m-1,r=s+1;
while(l+1<r){
int mid=(l+r)>>1;
if(mid*(n-1)>=s) r=mid;
else l=mid;
}
cout<<r;
return 0;
}