Problem Background

A common mistake when solving this problem is overly prioritizing minimizing the workload for earlier people, which could lead to some people being assigned no books (output 0 0). However, the problem test cases have been updated to guarantee every person gets at least one book to copy.

Problem Description

We have m ordered books that need to be assigned to k people for copying. All people have the same copying speed, a single book cannot be split between multiple people, and books assigned to the same person must be consecutive (you cannot assign the 1st, 3rd and 4th book to the same person for example).

Design an assignment scheme that minimizes the total copying time, where the total copying time is defined as the time taken by the person who copies the most pages.

Input Format

• First line: two intgeers m (number of books) and k (number of people)
• Second line: m integers, where the i-th integer is the number of pages of the i-th book.

Output Format

Output k lines, each line contains two integers: the starting and ending book number assigned to the i-th person. The starting numbers across the k lines must be in ascending order. If multiple valid schemes exist, choose the one that assigns the least possible workload too earlier people.

Sample Input

9 3
1 2 3 4 5 6 7 8 9

Sample Output

1 5
6 7
8 9

Constraints

1 ≤ k ≤ m ≤ 500

Solution Approach

The key constraint here is that books are ordered and must be assigned consecutively, which makes the binary search + greedy approach very suitable. While a cubic time dynamic programming approach is also feasible for this porblem's constraints, the binary search + greedy method is simpler to implement:

1. We use binary search to find the minimal possible maximum page count any single person can be assigned. The lower bound of the search is the page count of the longest single book, and the upper bound is the sum of pages of all books.
2. For each cendidate maximum page count during binary search, we use a greedy check starting from the last person: assign as many consecutive books as possible to the current person from the end of the unassigned book list, until adding another book would exceed the candidate maximum. This assignment method ensures that earlier people get the least possible workload when multiple valid solutions exist, which meets the problem's requirements.

Implemantation Code

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void read_input(T &val) {
    val = 0;
    char ch = getchar();
    int sign = 1;
    while (!isdigit(ch)) {
        if (ch == '-') sign = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        val = val * 10 + (ch - '0');
        ch = getchar();
    }
    val *= sign;
}

template <typename T, typename... Args>
inline void read_input(T &first, Args&... args) {
    read_input(first);
    read_input(args...);
}

const int MAX_BOOKS = 505;
int page_counts[MAX_BOOKS];
int assign_start[MAX_BOOKS], assign_end[MAX_BOOKS];
int total_books, total_people;

bool is_possible(int max_allowed_pages) {
    int current_book = total_books;
    for (int person = total_people; person >= 1; person--) {
        int remaining_pages = max_allowed_pages;
        assign_end[person] = current_book;
        while (current_book >= 1) {
            remaining_pages -= page_counts[current_book];
            if (remaining_pages < 0) {
                assign_start[person] = current_book + 1;
                break;
            }
            current_book--;
        }
    }
    return current_book == 0;
}

int main() {
    read_input(total_books, total_people);
    int left_bound = 0, right_bound = 0;
    for (int i = 1; i <= total_books; i++) {
        read_input(page_counts[i]);
        left_bound = max(left_bound, page_counts[i]);
        right_bound += page_counts[i];
    }
    
    while (left_bound < right_bound) {
        int mid = (left_bound + right_bound) >> 1;
        if (is_possible(mid)) {
            right_bound = mid;
        } else {
            left_bound = mid + 1;
        }
    }
    
    is_possible(left_bound);
    assign_start[1] = 1;
    for (int i = 1; i <= total_people; i++) {
        cout << assign_start[i] << " " << assign_end[i] << endl;
    }
    return 0;
}