二分

二分

upper_bound & lower_bound

"algorithm"里面提供了二分查找的函数 upper_bound 和 lower_bound。之前研究过，这里只简单说明下。

lower_bound 接受一个键值类型的参数。如果容器中某个元素的键值等于该参数，那么函数就返回指向该元素的迭代器。如果不存在这样的元素，则返回一个迭代器，指向第一个键值比参数大的元素。如果所有的元素的键值都比参数小，那么函数就返回容器的尾部，即等于end。

upper_bound 正好与 lower_bound相反。该函数返回的也是一个迭代器，指向第一个键值比参数大的元素，或者键值等于参数的元素。upper_bound返回的迭代器，指向键值大于参数的元素。如果所有元素的键值都比参数大，那么函数就返回容器尾部，即等于end。

基本模型

poj 1064

题意：给定 n 条绳子的长度，切割成 k 条长度相同的绳子，求这 k 条绳子每条最长能有多长？
PS：这题数据有问题

/*
ID: LinKArftc
PROG: 1064.cpp
LANG: C++
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
double cable[10010];
int main() {
    //    freopen("input.txt", "r", stdin);
    int n, k;
    while (~scanf("%d %d", &n, &k)) {
        for (int i = 1; i <= n; i ++) scanf("%lf", &cable[i]);
        double l = 0.0, r = 100010.0, mid;
        for (int j = 0; j < 100; j ++) {    //循环结束条件，根据精度选择循环次数
            mid = (l + r) / 2.0;
            int cur = 0;
            for (int i = 1; i <= n; i ++) cur += (int)(cable[i] / mid);
            if (cur >= k) l = mid;
            else r = mid;
        }
        printf("%.2f\n", double(int(l * 100)) / 100);
    }
    return 0;
}

poj 3122

/*
ID: LinKArftc
PROG: 3122.cpp
LANG: C++
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi = acos(-1.0);
const int maxn = 10010;
const double eps = 1e-8;
double cake[maxn];
int main() {
//    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T --) {
        int n, f;
        scanf("%d %d", &n, &f);
        for (int i = 1; i <= n; i ++) scanf("%lf", &cake[i]);
        double l = 0.0, r = 10010.0, mid;
        while (r - l > eps) {   //double型二分的另一种结束条件
            mid = (l + r) / 2.0;
            int cnt = 0.0;
            for (int i = 1; i <= n; i ++) cnt += (int)((pi * cake[i] * cake[i]) / (pi * mid * mid));
            if (cnt >= f + 1) l = mid;
            else r = mid;
        }
        printf("%.4f\n", pi * l * l);
    }
    return 0;
}

最大化最小值 & 最小化最大值

poj 2456

题意：给定 n 个牛舍的位置，使得 m 条牛的相邻两条牛之间的距离最小值最大化。

/*
ID: LinKArftc
PROG: 2456.cpp
LANG: C++
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int max_n = 100010;
int n, m;
int x[max_n];
int main() {
//    freopen("input.txt", "r", stdin);
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 1; i <= n; i ++) scanf("%d", &x[i]);
        sort(x + 1, x + n + 1);
        int l = 1, r = 1000000010, mid;
        while (r - l > 1) { //l， r都是整型，所以用这种方式跳出循环
            mid = (l + r) >> 1;
            int cnt = 1;
            int last = x[1];
            for (int i = 2; i <= n; i ++) {
                if (x[i] - last >= mid) {
                    cnt ++;
                    last = x[i];
                }
            }
            if (cnt >= m) l = mid; //注意区间，左闭右开
            else r = mid;
        }
        printf("%d\n", l); //区间左值有效
    }
    return 0;
}

最大化平均值

poj 2976

题意：n 场考试中分别答对 a[i] 题，总题数分别为 b[i]，允许去掉 k 场考试，求能达到的最高准确率。
思路：这题不能直接按照 a[i] / b[i] 贪心做，二分答案 x， 使得 ∑a[i] / ∑b[i] >= x，所以 ∑a[i] / ∑b[i] - x >= 0, 即 ∑(a[i] - x*b[i]) >= 0， 所以对 a[i] - x * b[i] 从大到小排序，贪心选择前 n - k 个

/*
ID: LinKArftc
PROG: 2976.cpp
LANG: C++
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;
double a[maxn], b[maxn], c[maxn];
bool cmp(double a, double b) {
    return a > b;
}
int main() {
//    freopen("input.txt", "r", stdin);
    int n, k;
    while (~scanf("%d %d", &n, &k)) {
        if (n == 0 && k == 0) break;
        for (int i = 1; i <= n; i ++) scanf("%lf", &a[i]);
        for (int i = 1; i <= n; i ++) scanf("%lf", &b[i]);
        int tot = n - k;
        double l = 0.0, r = 1.0, mid;
        for (int i = 0; i < 100; i ++) {
            mid = (l + r) / 2;
            for (int j = 1; j <= n; j ++) c[j] = a[j] - mid * b[j];
            sort(c + 1, c + n + 1, cmp);
            double sum = 0.0;
            for (int j = 1; j <= tot; j ++) sum += c[j];
            if (sum >= 0.0) l = mid;
            else r = mid;
        }
        printf("%.0f\n", l * 100);
    }
    return 0;
}

poj 3111

与上一题类似

/*
ID: LinKArftc
PROG: 3111.cpp
LANG: C++
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 100010;
const double eps = 1e-8;
struct Node {
    int id;
    double v, w, c;
} jew[maxn];
bool cmp(Node a, Node b) {
    return a.c > b.c;
}
int main() {
//    freopen("input.txt", "r", stdin);
    int n, k;
    while (~scanf("%d %d", &n, &k)) {
        double l = 0.0, r = 0.0, mid;
        for (int i = 1; i <= n; i ++) {
            scanf("%lf %lf", &jew[i].v, &jew[i].w);
            jew[i].id = i;
            r += jew[i].v;
        }
        while (fabs(l - r) > eps) {
            mid = (l + r) / 2.0;
            for (int i = 1; i <= n; i ++) jew[i].c = jew[i].v - mid * jew[i].w;
            sort(jew + 1, jew + n + 1, cmp);
            double sum = 0.0;
            for (int i = 1; i <= k; i ++) sum += jew[i].c;
            if (sum >= 0.0) l = mid;
            else r = mid;
        }
        printf("%d", jew[1].id);
        for (int i = 2; i <= k; i ++) printf(" %d", jew[i].id);
        printf("\n");
    }
    return 0;
}