算法题解(2)-二分

洛谷P1873 砍树

#include <stdio.h>

#define MAX(a, b) a>b?a:b
#define MIN(a, b) a>b?b:a

int main() {
    long long N, M, mid, length;
    scanf("%lld %lld", &N, &M);
    long long l = 0, s = 1000000000;
    long long height[N];
    for (int i = 0; i < N; ++i) {
        scanf("%lld", &height[i]);
        l = MAX(height[i], l);
        s = MIN(height[i], s);
    }
    mid = s + ((l - s) >> 1);

    while (s + 1 < l) {
        length = 0;
        for (int i = 0; i < N; ++i) {
            if (mid < height[i]) length += height[i] - mid;
        }
        if (length >= M) {
            s = mid;
            mid = s + ((l - s) >> 1);
        } else {
            l = mid;
            mid = s + ((l - s) >> 1);
        }
    }
    printf("%lld", mid);
    return 0;
}

洛谷P2249 【深基13.例1】查找

就是写二分，但是要注意输出最左边，也就是最小的，怎么找出左边界需要想一下（于是我一直wa

#include <bits/stdc++.h>

int find(int arr[], int len, int value) {
    int l = 1, r = len;
    int mid;
    while (l<r) {
        mid =l + (r-l)/2;
        if (arr[mid] < value)
            l = mid+1;
        else
            r = mid;
    }
    if (arr[l]==value)
    return l;
    else return -1;
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    int number[n+3];
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&number[i]);
    }
    int value;
    int index;
    for (int i = 0; i < m; ++i) {
        scanf("%d",&value);
        index=find(number,n,value);
        printf("%d ",index);
    }
    return 0;
}

洛谷P1678 烦恼的高考志愿

#include <bits/stdc++.h>

int min(int a,int b){
    int min;
    if (a<b)min=a;
    else min=b;
    return min;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int school[n+5];
    for (int i = 0; i < n; ++i) {
        scanf("%d",&school[i]);
    }
    std::sort(school,school+n);
    int stu[m+5];
    for (int i = 0; i < m; ++i) {
        scanf("%d",&stu[i]);
    }
    int sum = 0;
    for (int i = 0; i < m; ++i) {
        int l=0,r=n;
        while(l<r){
            int mid=(l+r)/2;
            if(school[mid]<=stu[i]){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        if(stu[i]<=school[0]){
            sum+=school[0]-stu[i];
        }
        else{
            sum+=min(abs(school[l-1]-stu[i]),abs(school[l]-stu[i]));
        }
    }
    printf("%d",sum);
    return 0;
}

P2440 木材加工

和砍树问题的思路一样，另写一个函数来判断是否符合要求，然后用二分法确定最大的值即可

#include <bits/stdc++.h>

using namespace std;

long long n, k;
long long a[1000005];

bool jd(long long x) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i] / x;
    }
    if (sum>=k){
        return true;
    }
    return false;
}

int main() {
    scanf("%lld%lld",&n,&k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld",&a[i]);
    }

    long long l = 0, r = 100000001;
    long long mid;

    while (l + 1 < r) {
        mid = l+(r-l)/2;
        if (jd(mid)) {
            l = mid;
        }
        else r = mid;
    }
    printf("%lld",l);
    return 0;
}

P2678 跳石头

同样的二分套路，这里定义了所在石头和下一个石头，mid大于间距时，将石头搬走，同时计数，mid小与或等于间距时，进入下一个石头。当搬走的总数要小于预计的数目时，证明mid偏小，将left右移，否则right左移，最终得到正确的mid。

#include <bits/stdc++.h>

long num[100000];
long l,n,m,dis=0,first=0,end;
int jd(long mid){
    long sum=0;
    int i=1;
    int temp=0;
    while(i <= n){
        first=num[temp];
        end=num[i];
        dis=end-first;
        if (dis<mid){
            sum++;
        } else temp=i;
        i++;
    }
    if (sum<=m){
        return 1;
    } else return 0;
}

int main(){
    scanf("%ld%ld%ld",&l,&n,&m);
    num[0]=0;
    for (long i = 1; i <= n; ++i) {
        scanf("%ld",&num[i]);
    }
    long left=0,right=l,mid,rst;
    while (left<=right){
        mid=left+(right-left)/2;
        if (jd(mid)){
            rst=mid;
            left=mid+1;
        }else right=mid-1;
    }
    printf("%ld",rst);
}