玩命加载中 . . .

洛谷官方题单——二分搜索和二分答案题解

编程算法题解 洛谷 二分
算法和程序设计
发布日期:   2020-04-29
文章字数:   2.7k
阅读时长:   12 分
阅读次数:  

在上一个题解中我就说过，二分的方法一定是需要找到某种单调性。因此只要能找到符合条件的单调性，那么在这一个部分一定可以考虑用二分来解决这部分的问题。

题目0：查找

题目的单调性很简单，单调性就是数据是递增的，那么我们直接二分就行了，注意你数组从0开始还是从1开始哦。

#include<stdio.h>
int memo[1000050], query[100050], n, m;
int search(int x) {
    int left = 0, right = n - 1;
    while (left < right) {
        int temp_mid = (left + (right - 1)) / 2;
        if (memo[temp_mid] >= x) right = temp_mid;
        else left = temp_mid + 1;
    }
    if (memo[left] == x) return left + 1;
    else return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &memo[i]);
    for (int i = 0; i < m; i++) scanf("%d", &query[i]);
    for (int i = 0; i < m; i++) printf("%d ", search(query[i]));
    return 0;
}

题目1：A-B 数对

实际上这道题在题目说法不怎么好，应该要说至少这个数据是要递增的，否则不能二分。这道题最好的办法肯定是map。

map即映射，数学的函数懂吧，就是一个映射，所以你只要map构建的时候，$map<A,B>$的第一个数是输入的数字$A$，第二个数字是$A-B=C$转换为$B=A-C$。注意，map实际上也是一个数组，但是你输入的是$A$，其数组存储的是$B$，但是你可以通过$A$去寻找$B$的位置。所以这样在搜索的时候，直接可以去调用$map[A]$去寻找对应的数的个数，最后累加即可。

同时注意数据范围，若需要的差为1，一半为1一半为2，则会超过int的范围= =（没错wa了一百年）

#include<iostream>
#include<map>
using namespace std;
int memo[200050];
map<int, int> book;
int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    int n, c;
    long long ans = 0;
    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> memo[i];
        book[memo[i]]++;
        memo[i] -= c;
    }
    for (int i = 1; i <= n; i++) ans += book[memo[i]];
    cout << ans << endl;
    return 0;
}

题目2：砍树

首先我们了解到，就是我们每砍一棵树，那么所需要的木材会逐渐减少，因此我们的答案是具备单调性的，因此可以使用二分来解决这道题。

#include<stdio.h>
long long tree[1000050];
long long max(long long x, long long y) { return x > y ? x : y; }
int main() {
    long long  n, m, tree_mmax = -1, left = 0, sum = 0;
    scanf("%lld%lld", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &tree[i]);
        tree_mmax = max(tree_mmax, tree[i]);
    }
    while (left <= tree_mmax) {
        sum = 0;
        long long temp_mid = (left + tree_mmax) >> 1;
        for (int i = 0; i < n; i++) if (tree[i] > temp_mid) sum += tree[i] - temp_mid;
        if (sum < m) tree_mmax = temp_mid - 1;
        else left = temp_mid + 1;
    }
    return 0 * printf("%lld\n", left - 1);
}

当然，实际上你可以使用直接排序，然后从后往前砍即可，代码略。

题目3：一元三次方程求解

如果你学过卡尔丹公式或者盛金公式，那么你可以直接用，但是我觉得你没学过（毕竟和抽代相关的内容，一般人不知道也正常）那么这里就可以考虑二分。

首先科普一下一个知识，若函数在某个区间内（无所谓开区间和闭区间，在极限的引入下都是无所谓的）有根，则对于其端点值的函数值乘积一定小于0，这样可以剪掉大部分无所谓的计算。

然后我们从$[-100,100]$依次从$-100$一个区间一个区间的循环就行了。

另解：牛顿迭代法

我们知道对于一个函数来说，只要在$x$处$f(x)$值不为无穷，那么其切线一定会与$x$轴相交，那么设其交点为$x_0$，那么交点$x_0$一定会和函数与$x$轴的交点靠近，于是使用这个方法可以无限逼近跟，最后只要其两点直接差小于给定的误差值$\epsilon$即可。

此处的单调性为：靠近根的距离是单调减少的。

#include<stdio.h>
double a, b, c, d;
double calculate(double x){
    return a * x * x * x + b * x * x + c * x + d;
}
int main(){
    double left, right, m, fx_left, fx_right;
    int cnt = 0;
    scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
    for (int i = -100; i < 100; i++){
        left = i, right = i + 1;
        fx_left = calculate(left), fx_right = calculate(right);
        if (fx_left == 0) {
            printf("%.2lf ", left);
            cnt++;
        }
        if (fx_left * fx_right < 0){
            while (right - left >= 0.001){
                m = (left + right) / 2;
                if (calculate(m) * calculate(right) <= 0) left = m;
                else right = m; 
            }
            printf("%.2lf ", right);
            cnt++;
        }
        if (cnt == 3) break;
    }
    return 0;
}

题目4：烦恼的高考志愿

将学校排序，然后每个学生找最靠近学校分数线的位置，然后前后最差比较即可。

单调性在于学校的分数被我们认为的弄成了有序。

#include<stdio.h>
#include<algorithm>
#include<math.h>
int school[1000050], students[1000050];
int min(int x, int y) { return x < y ? x : y; }
int main(){
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    int m, n, ans = 0;
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) scanf("%d", &school[i]);
    for (int i = 0; i < n; i++) scanf("%d", &students[i]);
    std::sort(school, school + m);
    for (int i = 0; i < n; i++){
        int left = 0, right = m;
        while (left < right){
            int mid = (left + right) / 2;
            if (school[mid] <= students[i]) left = mid + 1;
            else right = mid;
        }
        if (left > m) left = m;
        //printf("%d %d %d %d %d %d\n", school[1],students[i],left,school[left - 1],school[left], ans);
        if (students[i] <= school[0]) ans += school[0] - students[i];
        else ans += min(abs(school[left - 1] - students[i]), abs(school[left] - students[i]));
    }
    return 0 * printf("%d", ans);  
}

题目5：木材加工

这里我们了解到，所有的答案一定小于原木和除以需要的原木段，因此我们可以将答案二分。

这里的单调性是答案只会单调减小。

#include<stdio.h>
using namespace std;
int memo[100005];
int n, k;
int check(int x) {
    int temp_sum = 0;
    for (int i = 1; i <= n; i++) {
        temp_sum += (memo[i] / x); 
        if (temp_sum >= k) return 1;
    }
    return 0;
}
int binary_ans(int left, int right) {
    if (right <= left) return left;
    int mid = (right + left + 1) / 2;
    if (mid == 0) return 0;
    if (check(mid)) return binary_ans(mid, right);
    return binary_ans(left, mid - 1);
}
int main() {
    int sum = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &memo[i]);
        sum += memo[i];
    }
    int right = sum / n, left = 0;
    int ans = binary_ans(left, right);
    if (ans < 1) return 0 * printf("0\n");
    else return 0 * printf("%d\n", ans);
}

题目6：跳石头

题目要求选手们在比赛过程中的最短跳跃距离尽可能长，说明了我们要的答案的单调性——在某种意义上是递增的（在最小值满足的情况下，逐渐增大，则到了不满足的情况下，那么在不满足之前的情况下就是答案）。

#include <stdio.h>
int memo[500050];
int main() {
    int L, N, M, left, right, mid, ans = 0;
    scanf("%d%d%d", &L, &N, &M);
    for (int i = 1; i <= N; i++)scanf("%d", &memo[i]);
    left = 0, right = L;
    while (left <= right) {
        mid = (right + left + 1) / 2;
        int pos = 0, cnt = 0;
        for (int i = 1; i <= N; i++) {
            if (memo[i] - memo[pos] < mid) cnt++;
            else pos = i;
        }
        if (cnt <= M) ans = mid, left = mid + 1;
        else right = mid - 1;
    }
    return 0 * printf("%d\n", ans);
}

题目7：路标设置

还是一道二分答案，很典型的就是空旷指数最小值一定大于等于0（全满为0），那么我们只需要找到一个最大的，然后不断的把答案二分即可。

#pragma warning(disable:4996)
#include<stdio.h>
int L, N, K;
int memo[100005];
bool check(int mid) {
    int cnt = 0;
    for (int i = 0; i <= N; i++) {
        if (memo[i + 1] - memo[i] > mid) {
            cnt += (memo[i + 1] - memo[i]) / mid;
            if ((memo[i + 1] - memo[i]) % mid == 0) cnt--;
        }
        if (cnt > K) return false;
    }
    return true;
}
int main() {
    scanf("%d%d%d", &L, &N, &K);
    for (int i = 1; i <= N; i++) scanf("%d", &memo[i]);
    int left = 0, right = L + 5, ans = 0;
    memo[0] = 0,memo[N + 1] = L;
    while (left < right) {
        int mid = (left + right) / 2;
        if (check(mid)) right = mid;
        else left = mid + 1;
    }
    return 0 * printf("%d\n", left);
}

题目8：数列分段 Section II

分析题目，求最大值的最小化，直接二分答案，于是我们需要考虑如何check答案是否可行。

考虑贪心：

  1. 能加的就加上，不能则新开一个序列：

  2. 对于二分的值x，我们从数列从前往后扫：

    1. 若sum大于了当前x，我们便赋值当前元素到sum，并且新的序列+1；
    2. 否则就sum累加；

  3. 最后只需判断序列数是否大于等于输入的m就行了。

#include<stdio.h>
using namespace std;
int n, m, memo[100005];
int max(int x, int y) { return x > y ? x : y; }
bool check(int x){
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; i++){
        if (sum + memo[i] <= x) sum += memo[i];
        else sum = memo[i], cnt++;
    }
    return cnt >= m;
}
int main(){
    int left, right;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)scanf("%d", &memo[i]), left = max(left, memo[i]), right += memo[i];
    while (left <= right){
        int mid = left + right >> 1;
        if (check(mid)) left = mid + 1;
        else right = mid - 1;
    }
    return 0 * printf("%d\n", left);
}

题目9：银行贷款

实际上锁定一个收益率区间然后二分答案就行了（注意存在低于1的收益率）。

#include<stdio.h>
#include<math.h>
using namespace std;
int main() {
    double n, m, k, left = 0.0, right = 10.0;
    scanf("%lf%lf%lf", &n, &m, &k);
    while (right - left >= 0.0001) {
        double mid = (left + right) / 2;
        if ((pow(1.0 / (1.0 + mid), k) >= (1 - n / m * mid))) right = mid;
        else left = mid;
    }
    return 0 * printf("%.1lf\n", left * 100);
}

题目10：kotori的设备（蓝题预警）

二分时间：

  1. 验证的设备使用时间，若设备已有的能量大于使用时间需要的能量，忽略该设备；

  2. 否则充电，设备已有的能量等于使用时间需要的能量，并减去移动电源里设备需要的能量；

  3. 最后比较需要的能量总和和充电器最多提供的能量。

#pragma warning(disable:4996)
#include<stdio.h>
using namespace std;
int n;
double a_sum, a[100050], b[100050], p;
int check(double temp_ans) {
    double temp_all = temp_ans * p, temp_sum = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] * temp_ans <= b[i]) continue;
        temp_sum += (a[i] * temp_ans - b[i]);
    }
    return temp_sum <= temp_all;
}
int main() {
    double left = 0.0, right = 1e10;
    scanf("%d%lf", &n, &p);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &a[i], &b[i]);
        a_sum += a[i];
    } 
    if (a_sum <= p)return 0 * printf("-1\n");
    while (right - left >= 1e-6) {
        double mid = (right + left) / 2;
        if (check(mid)) left = mid;
        else right = mid;
    }
    return 0 * printf("%.5lf\n", left);
}

吐槽下最后一道题的坑，这精度卡的。

  1. 在九十分卡了十来分钟的a_sum必须是double，否则你必然WA两个点；
  2. 然后二分区间1E10，少了就会95分= =。

实际上二分还是很好写的，如果是二分搜索直接写，二分答案就是需要写出一个合适的check函数，然后就可以开心做好二分了。

文章作者: AleXandrite
文章链接: https://astrojoke.github.io/2020/04/29/luo-gu-guan-fang-ti-dan-er-fen-cha-zhao-yu-er-fen-da-an-ti-jie/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 AleXandrite !
编程算法题解 洛谷 二分
赏
  目录