蓝桥杯省赛无忧 第二章 基础算法 课件31 二分

01 二分简介

02 整数二分

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int data[200];
  for(int i=0;i<200;i++){
    data[i]=4*i+6;
  }
  int find;
  cin>>find;
  int l=0,r=200;
  while(l+1!=r){
    int mid=(l+r)/2;
    if(data[mid]>=find) r=mid;
    else l=mid;
  }
  cout<<r;
  return 0;
}

03 浮点二分

04 二分答案

#include<bits/stdc++.h>
using namespace std;
int len,n,m;
int stone[50005];

bool check(int d){
    int num=0;
    int pos=0;
    for(int i=1;i<=n;i++)
    if(stone[i]-pos<d)
    num++;
    else
    pos = stone[i];
    if(num<=m) return true; //最短跳跃距离太小了
    else return false;
}
int main(){
    cin>>len>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>stone[i];
    int l=0,r=len,mid;
    while(l<r){
        mid = (l+r+1)/2;
        if(check(mid))
        l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll x[N];
int check(ll mid,int n){
  ll sum=0,now=0;
  for(int i=1;i<=n;i++){
    if(now&&(x[i]-now)<mid)continue;  
//判断有没有种树，没有种树的话先种树，然后才能求间隔
    sum++;
    now=x[i];
  }
  return sum;  //返回当前间隔下种树的数量
}

int main()
{
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>x[i];
  }
  sort(x+1,x+1+n);
  ll l=0,r=1e9+10;
  while(l+1!=r){
    ll mid=(l+r)/2;
    if(check(mid,n)<m) r=mid;    //如果返回的值比m小则说明mid太大了
    else l=mid; 
  }
  cout<<l;

  return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
bool check(int mid){
    int count=0;
    for(int i=1;i<=n;i++) count+=min(m,mid/i);
    if(count>=k)    return 1;
    else return 0;
}
signed main(){
    
    cin>>n>>m>>k;
    int l=0,r=n*m+1,ans=0;
    while(l+1!=r){
        int mid=(l+r)/2;
        if(check(mid))  r=mid;
        else l=mid;
    }
    cout<<r;
    return 0;
}