二分算法（二分答案/最小化最大值/最大化最小值/第K小）By 灵茶山艾府
AI-摘要
切换
Tianli GPT
AI初始化中...
介绍自己
生成本文简介
推荐相关文章
前往主页
前往tianli博客
二分答案
int hIndex(vector<int>& q) {
int n=q.size();
int l=1,r=n;
while(l<=r){
int mid=(l+r)/2;
if(q[n-mid]>=mid) l=mid+1;
else r=mid-1;
}
return l-1;
}
- 1283. 使结果不超过阈值的最小除数 1542
int smallestDivisor(vector<int>& q, int mx) {
int l=1,r=*max_element(q.begin(),q.end());
while(l<=r){
int mid=l+r>>1,sum=0;
for(auto t:q){
sum+=ceil((double)t/mid);
}
if(sum<=mx) r=mid-1;
else l=mid+1;
}
return l;
}
- 2187. 完成旅途的最少时间 1641
long long minimumTime(vector<int>& q, int tt) {
long long l=1,r=1e14+10;
while(l<=r){
long long mid=l+r>>1;
long long trips=0;
for(auto t:q) trips+=mid/t;
if(trips>=tt) r=mid-1;
else l=mid+1;
}
return l;
}
- 2226. 每个小孩最多能分到多少糖果 1646
int maximumCandies(vector<int>& q, long long k) {
int l=1,r=1e7;
while(l<=r){
int mid=l+r>>1;
long long res=0;
for(auto t:q) res+=t/mid;
if(res>=k) l=mid+1;
else r=mid-1;
}
return r;
}
- 1870. 准时到达的列车最小时速 1676
int minSpeedOnTime(vector<int>& q, double h) {
int l=1,r=1e7,n=q.size();
while(l<=r){
int mid=l+r>>1;
double res=0;
for(int i=0;i<n-1;i++)
res+=ceil(q[i]*1.0/mid);
res+=q[n-1]*1.0/mid;
if(res<=h) r=mid-1;
else l=mid+1;
}
return l>0&&l<=1e7?l:-1;
}
- 1011. 在 D 天内送达包裹的能力 1725
int shipWithinDays(vector<int>& q, int d) {
int l=*max_element(q.begin(), q.end());
int r=5*5*1e6;
while(l<=r){
int mid=l+r>>1;
int res=1,tmp=0;
for(int i=0;i<q.size();i++){
if(tmp+q[i]>mid){
++res,tmp=0;
}
tmp+=q[i];
}
if(res<=d) r=mid-1;
else l=mid+1;
}
return l;
}
- 875. 爱吃香蕉的珂珂 1766
int minEatingSpeed(vector<int>& q, int h) {
long long l=1,r=1e13+10;
while(l<=r){
long long mid=l+r>>1;
long long sum=0;
for(auto t:q){
sum+=ceil(t*1.0/mid);
}
if(sum<=h) r=mid-1;
else l=mid+1;
}
return l;
}
- 1898. 可移除字符的最大数目 1913
bool check(string as,string p){
//双指针判断p是否为as的非连续子序列
int t=0;
for(int i=0;i<as.length();i++){
if(t!=p.length()&&as[i]==p[t])
t++;
}
return t==p.length();
}
int maximumRemovals(string s, string p, vector<int>& re) {
int n=re.size(),l=1,r=n;
while(l<=r){
int mid=l+r>>1;
string as=s;
for(int i=0;i<mid;i++){
as[re[i]]=' ';
}
if(check(as,p)) l=mid+1;
else r=mid-1;
}
return r;
}
- 1482. 制作 m 束花所需的最少天数 1946
int getm(vector<int>& q,int mid,int k){
int ans=0,tmp=0;
for(int i=0;i<q.size();i++){
tmp+=mid>=q[i];
if(tmp==k) ++ans,tmp=0;
if(mid<q[i]) tmp=0;
}
return ans;
}
int minDays(vector<int>& q, int m, int k) {
int l=1,r=1e9;
while(l<=r){
int mid=l+r>>1;
//查找mid天后合法的连续k个长的不相交子数组个数
if(getm(q,mid,k)>=m) r=mid-1;
else l=mid+1;
}
return l>1e9?-1:l;
}
- 1642. 可以到达的最远建筑 1962
bool check(priority_queue<int,vector<int>,greater<int>> &d, int b, int l){
if(l>=d.size()) return true;
int cnt=0;
while(d.size()!=l){
cnt+=d.top();
d.pop();
}
return b>=cnt;
}
int furthestBuilding(vector<int>& q, int bricks, int ladders) {
int n=q.size(),l=0,r=n-1;
while(l<=r){
int mid=l+r>>1;
priority_queue<int,vector<int>,greater<int>> d;
for(int i=1;i<=mid;i++){
int t=q[i]-q[i-1];
if(t>0) d.push(t);
}
if(check(d,bricks,ladders)) l=mid+1;
else r=mid-1;
}
return r;
}
- ⭐2258. 逃离火灾 2347
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
//判断mid分钟后能否到达安全屋
bool check(vector<vector<int>> &grid, int mid){
int m=grid.size(),n=grid[0].size();
vector<vector<int>> fired(m,vector<int>(n));
vector<pair<int,int>> f;
//初始化矩阵中火的位置
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(grid[i][j]==1){
fired[i][j]=true;
f.emplace_back(i,j);
}
//火的多源bfs
auto onfire=[&](){
vector<pair<int,int>> nf;
for(auto &[i,j]:f){
for(auto &[dx,dy]:dirs){
int x=i+dx,y=j+dy;
if( 0<=x&&x<m && 0<=y&&y<n && !fired[x][y] && grid[x][y]==0 ){
fired[x][y]=true;
nf.emplace_back(x,y);
}
}
}
f=move(nf);
};
//火在mid分钟内扩散
while(mid--&&!f.empty()) onfire();
if(fired[0][0]) return false;
//mid分钟后的人火博弈
vector<vector<int>> vis(m,vector<int>(n));
vis[0][0]=true;
vector<pair<int,int>> q{{0, 0}};
while(!q.empty()){
vector<pair<int,int>> nq;
for(auto &[i,j]:q){
if(fired[i][j]) continue;
for(auto &[dx,dy]:dirs){
int x=i+dx,y=j+dy;
if( 0<=x&&x<m && 0<=y&&y<n && !fired[x][y] && grid[x][y]==0 && !vis[x][y] ){
if(x==m-1&&y==n-1) return true;
vis[x][y]=true;
nq.emplace_back(x,y);
}
}
}
q=move(nq);
onfire();
}
return false;
}
int maximumMinutes(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
int l=0,r=m*n;
while(l<=r){
int mid=l+r>>1;
if(check(grid,mid)) l=mid+1;
else r=mid-1;
}
return r==m*n?1000000000:r;
}
最小化最大值
- 2064. 分配给商店的最多商品的最小值 1886
int minimizedMaximum(int n, vector<int>& q) {
int l=1,r=1e5;
while(l<=r){
int mid=l+r>>1;
int ans=0;
for(auto t:q)
ans+=ceil(t*1.0/mid);
if(ans<=n) r=mid-1;
else l=mid+1;
}
return l;
}
- 1760. 袋子里最少数目的球 1940
int minimumSize(vector<int>& q, int ms) {
int l=1,r=1e9;
while(l<=r){
int mid=l+r>>1;
int ans=0;
for(auto t:q)
ans+=ceil(t*1.0/mid)-1;
if(ans<=ms) r=mid-1;
else l=mid+1;
}
return l;
}
- 2439. 最小化数组中的最大值 1965
int minimizeArrayValue(vector<int>& q) {
auto check=[&](vector<int> q,int m){
//对于最大值m是否合法于q数组
long long cnt=0;
for(int i=q.size()-1;i>0;i--)
if(q[i]>=m) cnt+=q[i]-m;
else cnt-=min(cnt,1LL*m-q[i]);
return q[0]+cnt<=m;
};
int l=0,r=1e9;
while(l<=r){
int mid=l+r>>1;
if(check(q,mid)) r=mid-1;
else l=mid+1;
}
return l;
}
- ⭐2560. 打家劫舍 IV 2081
int minCapability(vector<int>& q, int k) {
auto check=[&](int mid){
//判断mid可行的窃取房间数量最少为k
int n=q.size();
vector<int> dp(n+2,0);
for(int i=2;i<n+2;i++){
if(q[i-2]>mid)
dp[i]=dp[i-1];
else
dp[i]=max(dp[i-1],dp[i-2]+1);
}
return dp[n+1]>=k;
};
int l=1,r=1e9;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
return l;
}
- 778. 水位上升的泳池中游泳 2097 相当于最小化路径最大值
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int swimInWater(vector<vector<int>>& grid) {
auto check=[&](int t){
int n=grid.size();
if(n==1&&t>=grid[0][0]) return true;
vector<vector<bool>> used(n,vector<bool>(n,false));
vector<pair<int,int>> p{{0,0}};
while(!p.empty()){
vector<pair<int,int>> np;
for(auto &[i,j]:p){
for(auto &[dx,dy]:dirs){
int x=i+dx,y=j+dy;
if( x>=0&&x<n &&
y>=0&&y<n &&
!used[x][y] &&
t>=grid[x][y]
){
if(x==n-1&&y==n-1) return true;
used[x][y]=true;
np.emplace_back(x,y);
}
}
}
p=move(np);
}
return false;
};
int l=grid[0][0],r=2500;
while(l<=r){
int t=l+r>>1;
if(check(t)) r=t-1;
else l=t+1;
}
return l;
}
- 2616. 最小化数对的最大差值 2155
int minimizeMax(vector<int>& q, int p) {
auto check=[&](int mid){
int n=q.size();
vector<int> dp(n+1,0);
for(int i=2;i<=n;i++){
if(q[i-1]-q[i-2]>mid)
dp[i]=dp[i-1];
else
dp[i]=max(dp[i-1],dp[i-2]+1);
}
return dp[n]>=p;
};
sort(q.begin(),q.end());
int l=0,r=1e9;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
return l;
}
- ⭐2513. 最小化两个数组中的最大值 2302
int gcd(int a,int b){return b!=0?gcd(b,a%b):a;}
long lcm(long a,long b){return a*b/gcd(a,b);}
int minimizeSet(int mod1, int mod2, int size1, int size2) {
auto check=[&](int x){
int cm1=x/mod1;
int cm2=x/mod2;
int gcm=x/lcm(mod1,mod2);
return x-cm1-cm2+gcm >= max(0,size1-cm2+gcm)+max(0,size2-cm1+gcm);
};
int l=1,r=INT_MAX;
while(l<=r){
int mid=l+((r-l)>>1);
if(check(mid)) r=mid-1;
else l=mid+1;
}
return l;
}
最大化最小值
- 1552. 两球之间的磁力 1920
int maxDistance(vector<int>& q, int m) {
auto check=[&](int mid){
//m个位置保证差值大于mid
int cnt=1,pre=0;
for(int i=1;i<q.size();i++){
if(q[i]-q[pre]>=mid)
cnt+=1,pre=i;
}
return cnt>=m;
};
sort(q.begin(),q.end());
int l=0,r=1e9;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
return r;
}
- 2861. 最大合金数 1981
int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
//返回各种机器制作mid个合金所需的最低预算
auto check=[&](int m){
//枚举台子
for(int i=0;i<k;i++){
long long res=0;
for(int j=0;j<n;j++){
res+=max(0L,(1L*m*composition[i][j]-stock[j])*cost[j]);
}
if(res<=budget) return true;
}
return false;
};
int l=0,r=2*1e8;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
return r;
}
- ⭐2812. 找出最安全路径 2154
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int maximumSafenessFactor(vector<vector<int>>& grid) {
//初始化
int n=grid.size();
//标记1点，新建矩阵
vector<vector<int>> q(n,vector<int>(n,-1));
vector<pair<int,int>> p;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(grid[i][j])
q[i][j]=0,p.emplace_back(i,j);
//多源bfs1点
vector<vector<pair<int,int>>> groups = {p};
while(!p.empty()){
vector<pair<int,int>> np;
for(auto &[i,j]:p)for(auto &[dx,dy]:dirs){
int x=i+dx,y=j+dy;
if( x>=0&&x<n && y>=0&&y<n && q[x][y]==-1)
np.emplace_back(x,y),q[x][y]=groups.size();
}
groups.push_back(np),p=move(np);
}
//检查是否联通
auto check=[&](int mid){
if(q[0][0]<mid) return false;
vector<vector<bool>> used(n,vector<bool>(n,false));
vector<pair<int,int>> b{{0,0}};
used[0][0]=true;
while(!b.empty()){
vector<pair<int,int>> nb;
for(auto &[i,j]:b)for(auto &[dx,dy]:dirs){
int x=i+dx,y=j+dy;
if( x>=0&&x<n && y>=0&&y<n && !used[x][y] && q[x][y]>=mid ){
if(x==n-1&&y==n-1) return true;
used[x][y]=true,nb.emplace_back(x,y);
}
}
b=move(nb);
}
return false;
};
//二分
int l=1,r=n*n;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
return r;
}
- ⭐2528. 最大化城市的最小供电站数目 2236
long long maxPower(vector<int>& q, int d, int k) {
int n=q.size();
vector<long> sq(n+1,0),p(n);
for(int i=0;i<n;i++)
sq[i+1]=sq[i]+q[i];
for(int i=0;i<n;i++)
p[i]=sq[min(n,i+d+1)]-sq[max(i-d,0)];
auto check=[&](long mid){
vector<long> cq(n,0);
long long cnt=0,sum_c=0;
for(int i=0;i<n;i++){
sum_c+=cq[i];
long m=mid-p[i]-sum_c;
if(m>0){
cnt+=m;
if(cnt>k) return false;
//更新差分
sum_c+=m;
int j=i+d*2+1;
if(j<n) cq[j]-=m;
}
}
return true;
};
long long l=0,r=1e16;
while(l<=r){
long long mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
return r;
}
第 K 小/大（部分题目也可以用堆解决）
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n=matrix.size();
auto check=[&](int m){
int cnt=0;
for(int i=n-1,j=0;i>=0;i--){
while(j<n && matrix[i][j]<=m) j++;
cnt+=j;
}
return cnt>=k;
};
int l=matrix[0][0],r=matrix[n-1][n-1];
while(l<=r){
int mid=l+r>>1;
check(mid)?r=mid-1:l=mid+1;
}
return l;
}
vector<vector<int>> kSmallestPairs(vector<int>& q1, vector<int>& q2, int k) {
int n=q1.size(),m=q2.size();
auto check=[&](int mid){
long long cnt=0;
int j=m-1;
for(int i=0;i<n;i++){
while(j>=0 && q1[i]+q2[j]>mid)
j--;
cnt+=j+1;
if(cnt>=k) return true;
}
return false;
};
int l=q1[0]+q2[0],r=q1[n-1]+q2[m-1];
while(l<=r){
int mid=l+(r-l)/2;
if(check(mid)) r=mid-1;
else l=mid+1;
}
vector<vector<int>> res;
int j=m-1;
for(int i=0;i<n;i++){
while(j>=0 && q1[i]+q2[j]>=l) j--;
for(int t=0;t<=j&&k>0;t++,k--)
res.push_back({q1[i],q2[t]});
}
for(int i=0;i<n;i++){
int t=l-q1[i];
int x=lower_bound(q2.begin(),q2.end(),t)-q2.begin();
int y=upper_bound(q2.begin(),q2.end(),t)-q2.begin()-1;
if( 0<=x&&x<m&&t==q2[x] &&
0<=y&&y<m&&t==q2[y]){
int cnt=y-x+1;
while(cnt--){
res.push_back({q1[i],q2[y]});
k--;
if(k==0) return res;
}
}
}
return res;
}
int smallestDistancePair(vector<int>& q, int k) {
int n=q.size();
sort(q.begin(),q.end());
auto check=[&](int mid){
int i=0,cnt=0;
for(int i=0,j=1;i<n;i++){
while (j<n&&q[j]-q[i]<=mid) j++;
cnt+=j-i-1;
if(cnt>=k) return true;
}
return false;
};
int l=0,r=1e6;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
return l;
}
int kthSmallest(vector<vector<int>>& q, int k) {
int m=q.size(),n=q[0].size();
int cnt=0,mid=0;
function<void(int, int)> dfs = [&](int i,int sum){
if(cnt==k) return;
if(i==m){
cnt+=sum>=0;
return;
}
for(int j=0;j<n;j++){
int z=q[i][j]-q[i][0];
if(z>sum) break;
dfs(i+1,sum-z);
}
};
int l=0,r=0;
for(auto t:q)
l+=t[0],r+=t.back();
int init=l;
while(l<=r){
mid=l+r>>1,cnt=0;
dfs(0,mid-init);
if(cnt==k) r=mid-1;
else l=mid+1;
}
return l;
}
- 786. 第 K 个最小的素数分数 2169
vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
int n=arr.size();
double l=0,r=1;
while(true){
double mid=(l+r)/2;
vector<int> ans={0,1};
int cnt=0;
for(int i=-1,j=1;j<n;j++){
//查找临界大于mid
while(arr[i+1]*1.0/arr[j]<mid){
++i;
//arr i /arr j > 存储
if(arr[i]*ans[1]>arr[j]*ans[0])
ans={arr[i],arr[j]};
}
cnt+=i+1;
}
if(cnt==k) return ans;
cnt<k?l=mid:r=mid;
}
}
- ⭐2386. 找出数组的第 K 大和 2648
long long kSum(vector<int> &nums, int k) {
//求出非负数和sum，反转数组负数
//此时∀子数组都可以通过
//sum-包含正数/sum+未包含负数得到=>sum-未包含负数转正数得到
long long sum=0;
for(int &x:nums) x>=0?sum+=x:x*=-1;
ranges::sort(nums);
//转化数组后，数组的第K大和=sum-转化后数组第K小和
auto check=[&](long mid){
int cnt=1;
//dfs(i,s)表示已选子序列和为s，选或不选nums[i]
function<void(int,long long)> dfs=[&](int i,long long s){
if (cnt==k || i==nums.size() || s+nums[i]>mid) return;
else cnt+=1,dfs(i+1,s),dfs(i+1,s+nums[i]);
};
dfs(0,0);
return cnt>=k;
};
//二分
long long l=0,r=1e14;
while (l<=r){
long long mid=l+r>>1;
check(mid)?r=mid-1:l=mid+1;
}
return sum-l;
}
long long fun(vector<int>& a, vector<int>& b, long long x, bool greater){
long long res=0;
if(!a.size() || !b.size()) return 0;
for(int i=0,j=b.size()-1;i<a.size();++i) {
if(greater){
while(j>=0 && 1ll*a[i]*b[j]>=x) --j;
res+=b.size()-1-j;
}
else{
while(j>=0 && 1ll*a[i]*b[j]>x) --j;
res+=j+1;
}
}
return res;
}
long long kthSmallestProduct(vector<int>& q1, vector<int>& q2, long long k) {
//init
vector<int> neg1,pos1,neg2,pos2;
for(int v:q1) (v<0)?neg1.push_back(-v):pos1.push_back(v);
for(int v:q2) (v<0)?neg2.push_back(-v):pos2.push_back(v);
reverse(neg1.begin(), neg1.end());
reverse(neg2.begin(), neg2.end());
long long l=-1e10,r=1e10;
while(l<=r){
long long mid=l+r>>1,cnt=
fun(pos1, pos2, mid, false)
+ fun(neg1, pos2, -mid, true)
+ fun(pos1, neg2, -mid, true)
+ fun(neg1, neg2, mid, false);
if(cnt>=k) r=mid-1;
else l=mid+1;
}
return l;
}
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果