蓝桥杯16天刷题计划一一Day02

作者：blue

时间：2025.3.28

[TOC]

今天训练的内容是二分法，部分题目还是比较难度的（反正博主自己做的时候做的挺累的，博主太菜了）

对二分法不熟悉的同学可以先学习我这篇文章：

P2249 【深基13.例1】查找 - 洛谷 (luogu.com.cn)

首先来一道最直白的题目，在一个有序的数组中，查找某个元素第一次出现的位置，这个时候，我们就可以利用二分查找，每次查找到一个结果后，我们不能直接输出，而是应该将l=mid-1去找更左边的数，因为我们要查找的是元素第一次出现的位置。

#include <iostream>
using namespace std;
const int N=1e6+10;
int a[N];
int main()
{
   
    int n,m,x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
   
        scanf("%d",&a[i]);
    }
    while(m--)
    {
   
        scanf("%d",&x);
        int l=1,r=n;
        int ans=-1;
        //要查找x在a中第一次出现的编号
        while(l<=r)
        {
   
            int mid=(l+r)/2;
            if(a[mid]==x){
   
                ans=mid;
                r=mid-1;//看看更左边有没有 
            }
            else if(a[mid]<x){
   
                l=mid+1;
            }
            else if(a[mid]>x){
   
                r=mid-1;
            }
        } 
        cout<<ans<<" ";
    }
    return 0;
}

P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 (luogu.com.cn)

这是一道经典的二分答案的好题，我们可以二分砍树的高度，因为题目的要求是砍树的高度要尽量高，所以我们每次找到一个符合条件的高度后并不停止程序，而是让r=mid+1，看看有没有更高的高度是符合条件的。

#include <iostream>
#define int long long
using namespace std;
const int N=1e6+10;
int tree[N];
int n,m;
bool check(int mid){
   
    int sum=0;
    for(int i=1;i<=n;i++){
   
        if(tree[i]>mid){
   
            sum+=tree[i]-mid;
        }
    }
    if(sum>=m) return true;
    else return false;
}
signed main()
{
   
    cin>>n>>m;
    int ans=-1;
    int l=0x3f3f3f3f,r=-1;
    for(int i=1;i<=n;i++) //输入时提前寻找好边界，l是最矮的树，r是最高的树 
    {
   
        cin>>tree[i];
        if(tree[i]<l) l=tree[i];
        if(tree[i]>r) r=tree[i];
    }
    while(l<=r)
    {
   
        int mid=(l+r)/2;
        if(check(mid)){
   
            ans=mid;
            l=mid+1;
        }
        else{
   
            r=mid-1;
        }
    }
    cout<<ans;
    return 0;
}

P2440 木材加工 - 洛谷 (luogu.com.cn)

本题同样是二分答案，基本和前一道题的思路一样，在此不过多赘述。

#include <iostream>
using namespace std;
const int N=1e5+10;
int tree[N];
int n,k;
bool check(int mid){
   
    int sum=0;
    for(int i=1;i<=n;i++){
   
        sum+=tree[i]/mid;
    }
    if(sum>=k) return true;
    else return false;
}
int main()
{
   
    int ans=0;
    int l=1,r=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++) 
    {
   
        cin>>tree[i];
        r=max(r,tree[i]);
    }
    while(l<=r){
   
        int mid=(l+r)/2;
        if(check(mid)){
   
            ans=mid;
            l=mid+1;
        } 
        else{
   
            r=mid-1;
        }
    }
    cout<<ans;
    return 0; 
}

P1083 [NOIP 2012 提高组] 借教室 - 洛谷 (luogu.com.cn)

暴力解法：本题建议从暴力解法开始做起，因为题目还是比较冗长的，先把题意理解清楚，通过暴力法我们就可以比较好的理解题目。

#include <iostream>
#define int long long
using namespace std;
const int N=1e6+10;
int r[N];
int d[N];
int s[N];
int t[N];
signed main(){
   
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>r[i];//有n天，每天有ri个教室 
    for(int i=1;i<=m;i++) cin>>d[i]>>s[i]>>t[i];//有m份订单 
    int day;
    for(day=1;day<=m;day++){
   
        for(int j=s[day];j<=t[day];j++){
   
            r[j]-=d[day];
            if(r[j]<0){
   
                cout<<"-1"<<endl;
                cout<<day;
                return 0;
            }
        }
    }
    cout<<0;
}

二分+前缀合优化：通过暴力法后，我们明显能感觉到，本题我们可以直接去二分订单的数量，然后对于每个订单借教室的操作，我们可以利用差分，因为差分的应用场景是对一段区间中的数字做统一操作，这和借教室的逻辑是相同的，所以我们可以这样操作。

#include <iostream>
#include <cstring> 
#define int long long
using namespace std;
const int N=1e6+10;
int n,m;
int r[N];
int d[N];
int s[N];
int t[N];
int D[N];//差分数组 
int a[N];//原数组 
bool check(int mid)
{
   
    memset(D,0,sizeof(D));//注意清空 
    for(int i=1;i<=mid;i++){
   
        D[s[i]]+=d[i];
        D[t[i]+1]-=d[i];
    } 
    for(int i=1;i<=n;i++){
   
        a[i]=D[i]+a[i-1];
        if(a[i]>r[i]) return true;
    }
    return false;
}
signed main(){
   
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>r[i];//有n天，每天有ri个教室 
    for(int i=1;i<=m;i++) 
    {
   
        cin>>d[i]>>s[i]>>t[i];//有m份订单 
    }
    int ans=-1;
    int l=1,r=m;
    while(l<=r){
   //二分订单数量 
        int mid=(l+r)/2;
        if(check(mid))//租赁不合法 ，r=mid-1 ,看看有没有天数更小就不合法的 
        {
   
            r=mid-1; 
            ans=mid;
        }
        else//租赁合法，l=mid+1 ，看看放大天数会不会产生不合法的 
        {
   
            l=mid+1;
        }
    }
    if(ans==-1){
   
        cout<<0;
    } 
    else
    {
   
        cout<<"-1"<<endl;
        cout<<ans;
    }
    return 0;
}

P2678 [NOIP 2015 提高组] 跳石头 - 洛谷 (luogu.com.cn)

本题和下一题是两道非常类似的题目。针对这道题目我的思路是这样的，我们可以二分最小的跳跃距离，然后去模拟跳跃的过程，如果本次跳跃的距离小于最小跳跃距离那么就把这块石头移除掉，然后记录移除石头的次数，然后如果跳到终点那一下的跳跃距离要长于最小跳跃距离并且挪走石头的次数要少于或等于最大次数，那么这个最小跳跃距离就是合法的，那我们就将l=mid+1看看有咩有更加长的最小跳跃距离。

#include <iostream>
using namespace std;
const int N=5e4+10;
int a[N];
int L,n,m;
bool check(int mid){
   
    int cnt=0;
    int cur=0;//表示当前选手所在的位置 
    for(int i=1;i<=n;i++){
   
        if(a[i]-a[cur]<mid){
   //小于最小跳跃距离，就把这块石头挪走 
            cnt++;
        }
        else{
   
            cur=i;//表示跳到了i石头上 
        }
    } 
    if(cnt<=m&&(L-a[cur]>=mid)) return true;
    else return false; 
}
int main()
{
   
    int ans=-1;
    cin>>L>>n>>m;
    for(int i=1;i<=n;i++){
   
        cin>>a[i];
    }
    int l=0,r=L;
    while(l<=r)
    {
   
        int mid=(l+r)/2;
        if(check(mid)){
   
            l=mid+1;
            ans=mid;
        }
        else{
   
            r=mid-1;
        }
    }
    cout<<ans;
    return 0;
}

P10909 [蓝桥杯 2024 国 B] 立定跳远 - 洛谷 (luogu.com.cn)

本题和前一题是比较类似的也是去年的一道国赛题，一个比较毒的点是这个爆发跳，其实这个爆发跳就是多给一个机会增加检查点。

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int n,m;
bool check(int mid){
   
    int cnt=0;
    for(int i=1;i<=n;i++){
   
        if(a[i]-a[i-1]>mid){
   //跳不过去 
            int cur=a[i-1];
            while(cur+mid<a[i]){
   //看看要增加几个检测点，才能一步跳过去 
                cnt++;
                cur+=mid;
            }
        }
    }
    return cnt<=m+1;//爆发跳其实就相当于多增加一个检测点 
}
int main()
{
   
    int ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
   
        cin>>a[i];
    }
    int l=1,r=a[n];
    while(l<=r){
   
        int mid=(l+r)/2;
        if(check(mid)){
   
            ans=mid;
            r=mid-1;
        }
        else{
   
            l=mid+1;
        }
    }
    cout<<ans;
    return 0;
}