集训第四周（高效算法设计）B题 (二分查找优化题)

---恢复内容开始---

Description

 

Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so calledscribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.

Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered ) that may have different number of pages ( ) and you want to make one copy of each of them. Your task is to divide these books among k scribes, . Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers  such that i-th scriber gets a sequence of books with numbers between b_i-1+1 and b_i. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

Input 

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, . At the second line, there are integers  separated by spaces. All these values are positive and less than 10000000.

Output 

For each case, print exactly one line. The line must contain the input succession  divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character (`/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.

If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.

Sample Input 

2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100

Sample Output 

100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100

 这道题首先应该想好思路，这道题其实是一个找限值的过程，比如说一个排列，我划分很多的区间，要求每一个区间都不能大于某个值，设这个值为m，那么这个值最小应该是多少，以例1为例，最小应为900，以例2为例，最小应该为100，为什么？因为你有可能将排列中某一个值划为一个区间，如果你限值小于900，那么900就进不了任何区间，划分就会出问题了

同样我们还可以得出m最大值应该是排列相加的总和（把整个排列划为一个区间）。

既然找好了限值的范围，那么限值有什么用呢？可以使用限值作为划多少区间的依据，我可以从从限值的最小处枚举到最大处，直到限值正好可以使区间划分为k个（注意这里可能有个精度问题）。可是枚举的方法虽然可以找到需求的那个值，但是。。。

超时啊，

虽然数组的长度只有500，但是数组元素的最大值可达一千万，一千万乘以五百是什么概念？这样枚举时间复杂度为m*n，超时。。

最好的方法是二分查找进行优化，以限值去判断，如果说这个限值使得区间划分数大于k,那么限值肯定要再大一些，往右查，反之则往左查

这样的时间复杂度是mlogn，时间性能大大提高...

#include"iostream"
#include"algorithm"
#include"cstring"
#include"cstdio"
using namespace std;
int n,k;
int a[510];
long long tot;
int maxa;

void Init()
{
    cin>>n>>k;
    tot=0;
    maxa=-1;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        tot+=a[i];
        maxa=max(a[i],maxa);
    }
//sort(a,a+n);
}

int need(long long num)
{
    long long c=0;
    int sum=1;
    for(int i=0; i<n; i++) if(c+a[i]<=num) c+=a[i];
        else
        {
            c=a[i];
            sum++;
        }
    return sum;
}

void print(long long num)
{
    int last[510];
    long long done = 0;
    memset(last, 0, sizeof(last));
    int remain = k;
    for(int i = n-1; i >= 0; i--)
    {
        if(done + a[i] > num || i+1 < remain)
        {
            last[i] = 1;
            remain--;
            done = a[i];
        }
        else
        {
            done += a[i];
        }
    }
    for(int i = 0; i < n-1; i++)
    {
        printf("%d ", a[i]);
        if(last[i]) printf("/ ");
    }
    printf("%d
", a[n-1]);
}

void guess()
{
    long long l,r,m;
    l=maxa;
    r=tot;
    while(l<r)
    {
        m=l+(r-l)/2;
        if(need(m)<=k) r=m;
        else l=m+1;
    }
    print(l);
}

int main()
{
    int T,t;
    cin>>T;
    t=T;
    while(T--)
    {
        Init();
        guess();
    }
    return 0;
}