P1281 书的复制

P1281 书的复制

题目分析：

1. 求解复制时间（抄写页数最多的人用去的时间）最短
2. 转换为：长度为m的数列分为k段，每段和的最大值，如何分才能使得最大值最小

注意：

• 如果有多解，则尽可能让前面的人少抄写
• 前面的人少抄写，就尽可能的用后面的人，那么从后往前遍历，最后反转一下输出答案

代码如下:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

#define inf 0x3f3f3f3f
#define eps 1e-6
#define db double
#define ll long long
#define  mm(a,x) memset(a,x,sizeof a)
#define pii pair<int,int>
#define pb push_back
#define el endl
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define fgx cerr<<"-------------------------"<<endl
#define shutio ios::sync_with_stdio(false),cin.tie(0)
#define  mk make_pair
#define lowbit(x) (x) & (-x)
#define fi first
#define se second

const int N = 510;

int m,k;
int a[N];
int l,r;
vector<pii > ans;

bool check(int x){
    int tot = 1;
    int s = 0;
    for(int i = 1; i <= m; i ++ ){
        if(s + a[i] > x){
            s = 0;
            tot ++;
        }
        s += a[i];
    }
    return tot <= k;    
}

int main() {
    shutio;
    cin >> m >> k;
    for(int i = 1; i <= m; i ++ ){
        cin >> a[i];
        l = max(l,a[i]);
        r += a[i];        
    }
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    int maxx = l;
    int s = 0;
    l = r = m;
    for(int i = m; i >= 1; i -- ){
        if(s + a[i] > maxx){
            s = 0;
            l = i;
            ans.push_back({l + 1,r});
            r = l;
        }
        s += a[i];
    }
    ans.push_back({1,r});
    reverse(ans.begin(),ans.end());
    for(auto item : ans){
        cout<<item.fi<<" "<<item.se<<endl;
    }
    return 0;
}