二分法 与 ccfcsp 垦田计划202303-2

时间：2024-03-31 14:24:02

简单的二分查找

int search(vector<int> nums,int target) 
{
    int left = 0;
    int right = nums.size()-1;
    while (left <= right) {	 
        int mid = left + ((right - left) / 2); 
        if (nums[mid] == target) {
            return mid; 
        } else if (nums[mid] < target) {
            left = mid + 1;	 
        } else {	 
            right = mid - 1;	
        }
    } 
    return -1;
}

lower_bound 和 upper_bound

对于升序

前者是找第一个大于等于target的下标 

后者是找第一个大于target的下标

对于降序

前者是寻找第一个小于等于target的下标

后者是寻找第一个小于target的下标

他们中间的  左闭右开  区间就是所有的target  

eg. int index=lower_bound(nums.begin(), nums.end(), target);

下面给出升序数组下的伪代码     只是逻辑实现功能相同并不是源码

//lower_bound伪代码
//nums升序
l=0, r=nums.size();
while(l<r){
    mid=l+ (r-l)/2;
    if(nums[mid]>=target){
        r=mid;  
    }else{
        l=mid+1;
    }
}
return r; //由于l==r时退出循环, 返回l或者r均可
//upper_bound伪代码
//nums升序
l=0, r=nums.size();
while(l<r){
    mid=l+ (r-l)/2;
    if(nums[mid]>target){ //只有这里和lower_bound不同
        r=mid;  
    }else{
        l=mid+1;
    }
}
return r; //由于l==r时退出循环, 返回l或者r均可

note :

        1.需要注意 l,r 初值   对于lower_bound  upper_bound 我们是要找第一个大于或大于等于的位置,所以必须有 nums.size() 

        2.判断条件check   满足条件的时候取到mid而不是mid-1或者mid+1,这是逻辑决定的

        3.while(l<r)   不取等于

        因为在上一个问题中,我们需在找不到的时候,返回-1, 所以使用 left<=right  这个条件判断当前是不是区间,如果不是,说明没找到             

        而在这个问题中,我们是使用left==right跳出循环,夹出位置,也就是如果存在第一个大于等于target的位置,那么他就是left/right

        4.返回值取 l或者r 都行   因为这个时候l==r;

二分法实战: ccfcsp202303-2 垦田计划

        链接:  计算机软件能力认证考试系统

        我们需要找到最后一个(最大)在给定资源下可以实现的天数

        注意到对于 day  在 [k  , max (ti) i=1,2,3...]  存在一个天数 使得前面都实现不了 后面都可以实现,满足二分法的应用

//核心代码

l=k, r=max;
while(l<r){
    int mid=l+(r-l)/2;
    if(check(mid...)){
        r=mid;
    }else{
        l=mid+1;
    }
}
ans = r;

全部代码:

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

bool check(int day,int m,vector<pair<int,int>>& v){
    for(auto it:v){
        if(it.first>day){
            m-=(it.first-day)*it.second;
            if(m<0) return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m,k; cin>>n>>m>>k;
    vector<pair<int,int>> v(n);
    int big=INT_MIN;
    for(int i=0;i<n;i++){
        cin>>v[i].first>>v[i].second;
        big=max(big,v[i].first);
    }
    //使用二分法找到最后一个可以的位置
    //二分法关注
    // 1. l,r初值
    // 2. check(mid) true false之后 的更新
    // 3. while取不取等   如果最后left或者right选对了,取不取等都一样,但是会卡死循环
    int left=k,right=big;
    while(left<right){
        int mid= left+(right-left)/2;
        if(check(mid,m,v)){
            right=mid;
        }else{
            left=mid+1;
        }
    }
    
    cout<<right<<endl;
    return 0;
}