poj 1505 Copying Books

poj 1505 Copying Books

#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>#include <numeric>#include <algorithm>using namespace std;#define MAX_BOOK_NUM 505int book_num, scriber_num;long long book[MAX_BOOK_NUM];bool cut_before[MAX_BOOK_NUM];void input(){    scanf("%d%d", &book_num, &scriber_num);    for (int i = 0; i < book_num; i++)        scanf("%lld", &book[i]);}bool ok(long long a){    long long temp = 0;    int cnt = 1;    for (int i = 0; i < book_num; i++)    {        if (temp + book[i] <= a)        { temp += book[i]; continue;        }        temp = book[i];        cnt++;        if (cnt > scriber_num) return false;    }    return cnt <= scriber_num;}long long binary_search(){    long long l = *max_element(book, book + book_num);    long long r = accumulate(book, book + book_num, 0);    while (l < r)    {        long long mid = (l + r) / 2;        if (ok(mid)) r = mid;        else l = mid + 1;    }    return l;}void work(){    long long each = binary_search();    memset(cut_before, 0, sizeof(cut_before));    long long temp = 0;    int cnt = 0;    for (int i = book_num - 1; i >= 0; i--)    {        if (temp + book[i] <= each)        { temp += book[i]; continue;        }        cut_before[i + 1] = true;        temp = book[i];        cnt++;    }    int i = 0;    while (cnt < scriber_num - 1)    {        i++;        if (!cut_before[i])        { cut_before[i] = true; cnt++;        }    }}void output(){    printf("%lld", book[0]);    for (int i = 1; i < book_num; i++)    {        if (cut_before[i]) printf(" /");        printf(" %lld", book[i]);    }    putchar('n');}int main(){    int t;    scanf("%d", &t);    while (t--)    {        input();        work();        output();    }    return 0;}