二分答案基础：书的复制

书的复制

题目背景

大多数人的错误原因：尽可能让前面的人少抄写，如果前几个人可以不写则不写，对应的人输出 0 0 。

不过，已经修改数据，保证每个人都有活可干。

题目描述

现在要把 $m$ 本有顺序的书分给 $k$ 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

输入格式

第一行两个整数 $m,k$。

第二行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 本书的页数。

输出格式

共 $k$ 行，每行两个整数，第 $i$ 行表示第 $i$ 个人抄写的书的起始编号和终止编号。 $k$ 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

样例 #1

样例输入 #1

9 3
1 2 3 4 5 6 7 8 9

样例输出 #1

1 5
6 7
8 9

提示

$1\le k \le m \le 500$。

无论使用二分答案还是动态规划，最后都要使用贪心，“则尽可能让前面的人少抄写。”

二分答案做法（较简便）（识别使用二分答案的依据是：最大值的最小值）

#include <iostream>
using namespace std;
#include <vector>
#define maxsize 505
int a[maxsize]={0};
int m, k, sum = 0;
bool check(int x)
{
    int need=1,temp=x;
    for(int i=m-1;i>=0;i--)
    {
        if(temp>=a[i])temp-=a[i];
        else
        {
            temp=x-a[i];
            need++;
        }
    }
    if(need>k)return false;
    else return true;
}
int main()
{
    cin>>m>>k;
    for(int i=0;i<m;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }

    int i=sum/k,j=sum,mid,ans;
    while(i<=j)
    {
        mid=(i+j)/2;
        if(check(mid))
        {
            ans=mid;
            j=mid-1;
        }
        else i=mid+1;
    }
    int temp=ans;
    vector<int> t;
    t.push_back(m);
    for (int i = m - 1; i >= 0; i--)
    {
        if (temp >= a[i])
            temp -= a[i];
        else
        {
            temp = ans - a[i];
            t.push_back(i+2);
            t.push_back(i+1);
        }
    }
    t.push_back(1);
    for(int i=t.size()-1;i>=0;i-=2)
    {
        cout<<t[i]<<" "<<t[i-1]<<endl;
    }
    return 0;
}

dp的话这是区间dp

注意：leap是累计数组，通过数组之间元素相减在可以直接得出区间元素和。

动态数组的行列定义：

i~人数k：当前拥有的人手

j_{m当前讨论的范围为0}j

前两层循环遍历每一个格子；

状态转移方程

f [ i ] [ j ] = minE(t from 1 to j-1)( max{dp[i-1][t],leap[j]-leap[t] } )

上面的minE表示枚举取最小

#include <iostream>
using namespace std;
#include <vector>
#define maxsize 505
int main()
{
    int m,k,a[maxsize]={0},leap[maxsize]={0},dp[maxsize][maxsize]={0};
    cin>>m>>k;

    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
        if (i == 1)
            leap[i] =a[i];
        else leap[i] = leap[i-1]+a[i];
    }
    for(int i=1;i<=m;i++)
    {
        dp[1][i]=leap[i];
    }
    for(int i=2;i<=k;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j] = max(dp[i - 1][1], leap[j] - leap[0]);
            for(int t=1;t<j;t++)
            {
                if(max(dp[i-1][t],leap[j]-leap[t])<dp[i][j])
                    dp[i][j] = max(dp[i - 1][t], leap[j] - leap[t]);
            }
        }
    }
    int indeedmin=dp[k][m],i=m;
    vector<int> v;
    v.push_back(m);
    while (i>0)
    {
        if(indeedmin-a[i]>=0)
            indeedmin-=a[i];

        else 
        {
            indeedmin=dp[k][m]-a[i];
            v.push_back(i+1);
            v.push_back(i);
        }
        i--;
    }
    v.push_back(1);
    for(int i=v.size()-1;i>=0;i-=2)
        cout<<v[i]<<" "<<v[i-1]<<endl;
    return 0;
}