二分答案算法笔记

smallfang

2020 年 08 月 11 日

1051 次浏览

暂无评论

889字数

算法笔记

二分答案、一个非常优秀的$logn$算法。

顾名思义、二分答案就是通过不断地二分寻找答案。
也就是找最中间的点。

二分答案与二分的基本条件一样、但是二分答案通常需要check函数、表示检查mid值是否符合题目要求。以此来找到最优解。

而r与l的差通常使得二分答案难于写出、这里推荐使用r-l>= 5然后通过题目描述分别测试这5个数那个更符合要求。而check函数因人而异。

让我们来找一道习题练练手。

书的复制

我们首先要确认二分答案啥.
这道题我们需要二分复制时间。

最后的答案需要保证后面多写、前面少写。
因为题目中说尽量前面的少取

Code

// Problem: 书的复制

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 501;

int a[MAXN + 1];

int n, m;

bool check(int x)
{
    int cnt = 0, k = 1;
    for (int i = 1; i <= n; i ++ )
    {
        if (a[i] > x)
        {
            return false;
        }
        if (cnt + a[i] > x)
        {
            k ++;
            cnt = a[i];
        }
        else
        {
            cnt += a[i];
        }
    }
    return k <= m;
}

pair<int, int> res[10001];

void getans(int x)
{
    int k = m, f = 0;
    res[k].first = n;
    for (int i = n; i >= 1; i -- )
    {
        f += a[i];
        if (f > x)
        {
            f = a[i];
            res[k].second = i + 1;
            k --;
            res[k].first = i;
        }
    }
    res[1].second = 1;
    for (int i = 1; i <= m; i ++ )
    {
        printf("%d %d\n", res[i].second, res[i].first);
    }
}

int main()
{
    int l, r;
    scanf("%d%d", &n, &m);
    l = 1;
    r = 100001;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    while(r - l > 5)
    {
        int mid = (r + l) / 2;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    int res = 0;
    for (int i = l; i <= r; i ++ )
    {
        if (check(i))
        {
            res = i;
            break;
        }
    }
    getans(res);
    return 0;
}

Stop learning useless algorithm, go and learn binary search.

二分答案算法笔记