二分查找与二分答案

二分查找与二分答案

题目一

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


int n,m;

int a[1000010];
bool check(int x,int num) {
    if (x < num) return true;
    else return false;
}
int se(int x) {
    int l = 0,r = n+1;
    while (l+1 < r) {
        int mid = (l+r)/2;
        if (check(a[mid],x)) l = mid;
        else r = mid;
    }
    if (a[r] == x) return r;
    else return -1;
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    while (m--) {
        int num;
        cin >> num;
        int index = se(num);
        cout << index << " ";
    }
    return 0;
}

题目二

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


const int N = 100010;
int a[N];
int b[N];
int m,n;
int num;
int res;
bool isBlue(int x) {
    if (x <= num) return true;
    else return false;
}
void check() {
    int l = 0,r = m+1;
    while (l+1 < r) {
        int mid = (l+r) / 2;
        if (isBlue(a[mid])) l = mid;
        else r = mid;
    }
    if (num <= a[1]) res += a[1] - num;
    else res += min(abs(a[r]-num),abs(a[l]-num));
}
int main () {
    cin >> m >> n;
    for (int i = 1;i <= m;i++) {
        cin >> a[i];
    }
    sort(a+1,a+m+1);

    for (int i = 1;i <= n;i++) {
        cin >> num;
        check();
    }
    cout << res;
}

题目三

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


int n,m;
int a[1000010];

bool check(int x) {
    int sum = 0;
    for (int i = 1;i <= n;i++) {
        sum += a[i] - x > 0 ? a[i] - x:0;
    }
    if (sum < m) return false;
    else return true;
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    int l = 0,r = 2*1e5+10;
    while (l+1 < r) {
        int mid = (l+r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << l;
}

题目四

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


int n,m;
const int N = 1e8+10;
int a[N];

bool check(int x) {
    int sum = 0;
    for (int i = 1;i <= n;i++) {
        sum += a[i] / x;
    }
    if (sum < m) return false;
    else return true;
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    int l = 0,r = 1e8+10;
    while (l+1 < r) {
        int mid = (l+r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << l;
}

题目五

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


int n,m;
const int N = 1e5+10;
int a[N];
int sum[N];


int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        sum[i] += sum[i-1]+a[i];
    }
    int l = 0,r = 1e9;
    while (l+1 < r) {
        int mid = (l+r)/2;

        int ans = 0;
        int index = 0;
        for (int i = 1;i <= n;i++) {
            if (sum[i] - sum[index]> mid) {
                index = i-1;
                ans++;
            }
        }
        if (ans >= m) l = mid;
        else r = mid;
    }
    cout << r;
}