二分法问题合集

1.假定一个解判断是否可行

POJ 1064

#include <iostream>
#include <vector>
#define INF 10000
using namespace std;
int N, K;
vector<double> ropes;

bool C(double x) {
    int num = 0;
    for (int i = 0; i < N; i++) {
        num += (int)(ropes[i] / x);
    }
    return num >= K;
}

void slove() {
    double lb = 0, ub = INF;
    for (int i = 0; i < 100; i++) {
        double mid = (lb + ub) / 2;
        if (C(mid))
            lb = mid;
        else
            ub = mid;
    }
    printf_s("%.2f\n", floor(ub * 100) / 100);
}

int main()
{
    cin >> N >> K;
    double length;
    for (int i = 0; i < N; i++) {
        cin >> length;
        ropes.push_back(length);
    }
    slove();
    return 0;
}

二分法的结束判定：
在输出小数的问题中，一般会指定输出中小数点后面的位数，所以有必要设置合理的结束条件来控制精度，上面的题中达到了的精度范围，也可以设置类似ub-lb>EPS这样的条件。

2.最大化最小值（二分+贪心）

POJ 2456

Ｎ间小屋，Ｍ头牛，使得牛跟牛之间的距离最远，以防止牛打架。

#include <iostream>
#include <algorithm>
#include <cstdio>
#define MAX_N 100001
#define INF 20000
using namespace std;
int N, M;
int x[MAX_N];

bool C(int d) {
    int last = 0;
    for (int i = 1; i < M; i++) {
        int crt = last + 1;
        while (crt<N&&x[crt]-x[last]<d)
        {
            crt++;
        }
        if (crt == N) {
            return false;
        }
        last = crt;
    }
    return true;
}

void solve() {
    int lb = 0, ub = INF;
    while (ub - lb > 1) {
        int mid = (lb + ub) / 2;
        if (C(mid)) {
            lb = mid;
        }
        else {
            ub = mid;
        }
    }
    printf("%d\n", lb);
}

int main()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &x[i]);
    }
    sort(x, x + N );
    solve();
    return 0;
}

不断缩小可用值的范围，选取最大的值，贪心法+二分法

POJ 3258

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#define Max_N 50000
using namespace std;

int L, N, M;
vector<int> stones(Max_N);

bool C(int mid) {
    int last = 0;
    for (int i = 1; i < N +2 - M; ++i) {
        int current = last + 1;
        while (current<N+2&&stones[current]-stones[last]<mid)
        {
            ++current;
        }
        if (current == N+2) {
            return false;
        }
        last = current;
    }
    return true;
}

void solve() {
    sort(stones.begin(), stones.begin() + N+2);
    int lb = 0, ub = L+1;
    while (ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if (C(mid)) {
            lb = mid;
        }
        else {
            ub = mid;
        }
    }
    printf("%d\n", lb);
}

int main()
{
    scanf("%d %d %d", &L, &N, &M);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &stones[i]);
    }
    stones[0] = 0;
    stones[N+1] = L;
    solve();
    return 0;
}

POJ 3273

#include <iostream>
#include <cstdio>
#define Max_N 100000
using namespace std;
int Days[Max_N];
int N, M;

bool C(int mid) {
    int pig = 0;
    int t = 0;
    for (int i = 0; i < N; ) {
        t++;
        while ((i<N)&&(pig + Days[i] <= mid)) {
            pig += Days[i];
            i++;
        }
        pig = 0;
        if (t > M ) {
            return false;
        }
    }
    return true;
}

void solve() {
    int lb = 0, ub = 50000;
    while (ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if (C(mid)) {
            ub = mid;
        }
        else {
            lb = mid;
        }
    }
    printf("%d\n", ub);
}

int main()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &Days[i]);
    }
    solve();
    return 0;
}

POJ 3104

#include <iostream>
#define Max_N 10000000
#define INF 1000000000
using namespace std;

int n, k;
int a[Max_N];

//mid为时间
bool C(long long mid) {
    int wind = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] > mid) {
            int t = 0;
            do {
                t++;
                wind++;
            } while (mid+t*(k-1)<a[i]&&(wind<=mid));
            if (wind > mid)
                return false;
        }
    }
    return true;
}

void solve() {
    long long lb = 1, ub = INF;
    while (ub - lb > 1) {
        long long mid = (ub + lb) / 2;
        if (C(mid)) {
            ub = mid;
        }
        else {
            lb = mid;
        }
    }
    cout << ub << endl;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    cin >> k;
    solve();
    return 0;
}

3.最大化平均值

有n个物品的重量和价值分别是和。从中选出k个物品使单位重量的价值最大。

#include <iostream>
#include <algorithm>
#include <cstdio>
#define Max_N 1000000
#define INF 10010
using namespace std;

int n, k;
int w[Max_N], v[Max_N];

double y[Max_N];//v-x*w

bool C(double x) {
    for (int i = 0; i < n; ++i) {
        y[i] = v[i] - w[i] * x;
    }
    sort(y, y + n);

    double sum = 0;
    //计算从大到小k个数的和，若差小于0，则平均值不成立
    for (int i = 0; i < k; i++) {
        sum += y[n - i - 1];
    }
    return sum >= 0;
}

void solve() {
    double lb = 0, ub = INF;
    for (int i = 0; i < 100; i++) {
        double mid = (lb + ub) / 2;
        if (C(mid))
            lb = mid;
        else
            ub = mid;
    }
    printf("%.2f\n", ub);
}

int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &w[i], &v[i]);
    }
    solve();
    return 0;
}

一般先想到对物品按照单位价值排序，但是根据样例，这是不可行的。
解决方法变为，其中x为最大的平均单位价值，化简得，因此对这个式子的值进行贪心的由大到小选取k个。

转载于:https://www.jianshu.com/p/b15d51b62cec