蓝桥杯冲刺_二分(正在补题)

二分一定要是单调队列，单调才具有二段性

特征 最小值最大化 最大值最小化

15 届蓝桥杯 14 天省赛冲刺营 1 期 - M次方根 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h> 
using namespace std;

double n,l,r,mid;
double eps=1e-8;

bool check(double mid,int m){//m次根下
    double c=1;
    while(m){
        c=c*mid;//s次根 
        m--;//c是mid的3次方 
    }
//要与别的条件扯上关系 在这里就是与n本身扯上关系
    if(c>=n)//如果mid的3次方大于等于n 
        return true;//还可以再小 
    else//如果mid的3次方下雨n 
        return false;//需要更大 
}

int main(){
    int m;
    cin>>n>>m;
//设置二分边界
    l=0,r=n;
//实数二分
    while (l + eps < r)
    {//mid是a可以的值 
        double mid = (l + r) / 2;
        if (check(mid,m))r = mid;
        else l = mid;
    }
    //一般使用print
    //printf("%x.yf",n)
    //其中X是固定整数长度，小数点前的整数位数不够，会在前面补0
    //y是保留小数位数，不够补零
    printf("%.7f",l);
    return 0;
}

15 届蓝桥杯 14 天省赛冲刺营 1 期 - 分巧克力 - 蓝桥云课 (lanqiao.cn) 

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int h[N],w[N];
int n,k;
bool check(int mid){//最大边长是mid
  int cnt=0;
  for(int i=1;i<=n;i++){
    int len=h[i]/mid;
    int wid=w[i]/mid;
    cnt+=len*wid;
  }
  return cnt>=k;
}
void solve(){
  cin>>n>>k;
  for(int i=1;i<=n;i++)cin>>h[i]>>w[i];
  int l=0,r=1e5+7;
  while(l<r){
    int mid=(l+r+1)>>1;
      if(check(mid))l=mid;//还可以更多
      else r=mid-1;
  }
  cout<<l;
  return ;
}
int main(){
  int t=1;
  while(t--)solve();
  return 0;
}

1.跳石头 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+7;
int l,n,m;
int stones[N];
bool check(int mid){//最短跳跃距离
  int pos=0;//记录目前在哪个石头上目前在起点石头上
  int cnt=0;//搬走多少个石头
  for (int i = 1; i <= m+1; i++)
        if (stones[i] - stones[pos] < mid)
            cnt++;//小于最小跳跃距离就搬走石头i然后去看下一个石头
        else pos = i;//否则跳上
    if (cnt <= n) return true;//最短跳远距离mid还可以更大
    return false;
}
void solve(){
  cin>>l>>m>>n;//起点到终点的距离 岩石数 至多移走
  for(int i=1;i<=m;i++){
    cin>>stones[i];//表示第i个石头到起点stones[0]的距离
  }
  stones[m+1]=l;//终点石头
  int l=1,r=1e9+7;//最短的跳远距离
  while(l<r){
    int mid=(l+r+1)>>1;
    if(check(mid))l=mid;
    else r=mid-1;
  }
  cout<<l;
  return ;
}
int main(){
  int t=1;
  while(t--)solve();
  return 0;
}

1.解立方根 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h>
using namespace std;
double n;
double eps=0.0001;
bool check(double mid,int m){//m次方
  double res=1;
  while(m--){
    res*=mid;//得到这个数的m次方
  }
  if(res>=n)return true;
  else return false;
}
void solve(){
  cin>>n;
  double l=0,r=n;
  while(l+eps<r){
    double mid=(l+r)/2;//不能位运算了
    if(check(mid,3))r=mid;//还能更小
    else l=mid;
  }
  printf("%.3lf\n",l);
  return ;
}
int main(){
  int t=1;cin>>t;
  while(t--)solve();
  return 0;
}