[UVA] 714 - Copying Books

題意:
給你很多書的頁數，
要你分成n份後，頁數最多的那一份他的頁數要盡量小，
範例輸入:
9 3 //9本書，分3份
100 200 300 400 500 600 700 800 900 //9本書的頁數
可以這樣分
100 200 300  (總頁數=100+200+300=600)
400 500 600  (總頁數=400+500+600=1500)
700 800 900  (總頁數=700+800+900=2400)
頁數最多的那一份總頁數是2400

也可以這樣分
100 200 300 400 500   (總頁數=100+200+300+400+500=1500)
600 700   (總頁數=600+700=1300)
800 900   (總頁數=800+900=1700)
頁數最多的那一份總頁數是1700，
就比上一個分法少。

--------------------------------------------------

我的作法:
令P(x)為分成n堆後每一堆的總頁數都<=x，
回傳true表示可能，回傳false表示不可能(例如上面的範例，P(10)就是false)，
利用二分法，
lower=所有書當中頁數最多的(因為不管怎麼分堆，其中一堆一定有這本書的頁數)，
upper=所有書的頁數總和(全部分成一堆)，
用middle去帶入P(x)，
若P(middle)為true，表示x可以更小，
若為false，表示x應該要更大。

P(x):
在分堆的時候第一堆從最右邊的頁數先塞，
不能塞了就換下一堆，
在過程中可以先儲存'/'的位置!
另外需要注意的是:
剩餘書的數量要>=剩餘堆的數量，
因為每一堆都至少要有一本書

--------------------------------------------------

/* 20151004
 * hanting
 * UVa 714 - Copying Books
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm> //max_element
using namespace std;
#define MID(x,y) (x+y)/2
vector<int> page;
vector<int> group;
long long sumOfPage()//所有頁數的總和
{
    long long sum=0;
    for(int i=0;i<page.size();i++)
    {
        sum+=page[i];
    }
    return sum;
}
bool P(long long x)//各個堆的總數都小於等於x
{
    group.assign(group.size(),0);
    long long sum=0;
    int j=0;
    int i=page.size()-1;
    for(;i>=0;i--)
    {
        if(j>=group.size()) break;
        if(sum+page[i] <= x and i+1>=group.size()-j)//書的數量要大於等於scriber的數量
        {
            sum+=page[i];
            group[j]=i;//將'/'的位置紀錄
        }
        else
        {
            j++;
            i++;
            sum=0;
        }
    }
    return i==-1;
}
void solution()
{
    long long low=*std::max_element(page.begin(),page.end());//最小是所有書當中頁數最多的
    long long up=sumOfPage();//最大是所有書的頁數總和
    long long mid=MID(low,up);
    while(low<up)
    {
        if(P(mid))
        {
            up=mid;
            mid=MID(low,up);
        }
        else
        {
            low=mid+1;
            mid=MID(low,up);
        }
    }
    P(low);
    reverse(group.begin(),group.end());
    int j=1;
    for(int i=0;i<page.size();i++)
    {
        if(j<group.size() and i==group[j])
        {
            cout<<"/ ";
            j++;
        }
        cout<<page[i];
        if(i!=page.size()-1) cout<<" ";
        else cout<<endl;
    }
}
int main()
{
    int caseN;
    cin>>caseN;
    while(caseN--)
    {
        int bookN,groupN;
        cin>>bookN>>groupN;
        page.assign(bookN,0);
        group.assign(groupN,0);
        for(int i=0;i<bookN;i++)
        {
            cin>>page[i];
        }
        solution();
    }
    return 0;
}