抄写员

这个代码的控件写的太不好了， 注释有点符号格式就乱了， 真无语。。

〖题目描述〗
假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P
1，P2，…PM）。任务是将这M本书分给K个抄写员（K〈=M〉，每本书只能分配给一个抄写
员进行复制，而每个抄写员所分配到的书必须是连续顺序的。
意思是说，存在一个连续升序数列 0 = bo < b1 < b2 < … < bk-1 < bk = m，这样，第
I号抄写员得到的书稿是从bi-1+1到第bi本书。复制工作是同时开始进行的，并且每个抄写
员复制的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那
个抄写员的复制时间。试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽
可能小（如存在多个最优方案，只输出其中一种）。
(GDOI\'\'99 Books).

〖输入格式〗
第一行两个数m,k:表示书本数目与人数;第二行m个由空格分隔的整数,m本书每本的页数.


〖输出格式〗
共k行。每行两个整数：第I行表示第I抄写员抄的书本编号起止。

〖输入输出样例〗

输入样例
9 3
1 2 3 4 5 6 7 8 9

 

输出样例  

1 5
6 7
8 9

不好做的一题。

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

int split(int *books, int count, int group){
    if(books == NULL) return -1;
    int gcount = 0;
    int record[MAX][MAX] = {{0}};
    record[0][0] = books[0];
    int i = 1;
    for(;i<count;i++){
        record[gcount][i] = record[gcount][i-1]+books[i];
    }
        gcount++;
    for(;gcount<group;gcount++){
        i = gcount;
        for(;i<count; i++){
            //printf("i = %d \n", i);
            //get value;
            int max = books[i]>record[gcount-1][i-1]? books[i]:record[gcount-1][i-1];
            int t;
            for(t = gcount-1; t<i; t++){
                int right = record[0][i] - record[0][t];
                int left = record[gcount-1][t];
                int v = right>left?right:left;
                max = max<v?max:v;
                //printf("left = %d, right = %d \n", left, right);
            }
            record[gcount][i] = max;
            printf("fill (%d,%d) = %d \n", gcount, i, record[gcount][i]);
        }
    }
}
int main(){
    int books[] = {1,2,3,4,5,6,7,8,9};
    int count = sizeof(books)/sizeof(int);
    int group = 3;
    printf("%d \n", split(books, count, group));
}

 

 

 

曾经的回溯法备份。

my $m = 9;
my $k = 3;
my @books = (9,8,7,6,5,4,3,2,1);

#for array, sp can get the index of number. If you split the array @a at the index, you can get 2 arrays, whose max sum is the smallest
#this is just for optmize the last step. can be skipped and just enumrate all possiblities in the recursive function.
sub sp{
    my @a = @_;
    my ($value, $index);
    for(1..(@a-1)){
        my ($l, $r) = (0, 0);
        for(0..$_-1){
            $l+=$a[$_]
        }
        for($_..@a-1){
            $r+=$a[$_];
        }
        my $t = $l;
        $t = $r if($r>$l);
        if($t<$value or $value == 0){
            $value = $t;
            $index = $_;
        }
    }
    return $value, $index-1;
}

#$max is the sum restrict
#$starti means the start index of @books, where we try to create a new group from. This is determined by the last group's end index
#$count means the amount of left group need to fill
#@is is use to store the book start index and end index of every group.
sub f{
    my $max = shift;
    my $starti = shift;
    my $count = shift;
    my @is = @_;

    #if current sum restrict is large than success group's sum, it is not a good choice. So we drop it and return directly.
    #If $maxs(best choice's sum) is 0, it means there is no success group until now, so we continue
    if($max>$maxs and $maxs!=0){
        #print "$max > $maxs No Value !!! Drop it!!!\n";
        return;
    }

    #if only 2 group left, we use sp to get be best split of the left array
    if($count <= 2){

        #the books left, from $books[$starti] to end
        my @tbooks = @books;
        for(0..$starti-1){
            shift(@tbooks);
        }

        my ($v, $in) = sp(@tbooks);

        #if the max sum of the left 2 group is larger than the finished group, we place the max sum value.
        $max = $v if($v>$max);

     #push the end index of the last second group
        push(@is, $in+$starti);
        #push the start index of the last group
        push(@is, $in+$starti +1);
        #push the end index of the last group
        push(@is, $m-1);

        #if current groups's max sum is small than the current record, we replace, or we drop it.
        if($max<$maxs or $maxs == 0){
            $maxs = $max;
            @res = @is;
        }
        return;
    }

    #try all possible amount (from 1 book to $m-$starti-$count books) for current group !!!!!!!!!!!!!!!!!!!!!!!!!!that's wrong!!!!!!
    #why $m -$count? No group is empty, so we have $count groups need to fill, we should left $count books for other group.
    #$m-$starti means the amount of books left, which need to assign to $count worker.
    for my $c (1..$m-$starti - $count +1 ){
        my $t = 0;

        #create dumy array to store current choice.
        my @tis = @is;

        #calculate the sum of current group
        for(1.. $c){
            $t = $t + $books[$starti+$_-1];
        }

        #push the start index 0 if the groups are empty
        if(@tis == 0){
            push(@tis, 0);
        }
        #push the end index of the group.
        push(@tis, $starti+$c-1);

        #push the start index of next group;
        push(@tis, $starti+$c);

        #modify the max sum of current groups if current group's sum is max.
        $max = $t if($t>$max);

        #we assign $c book from the start index $starti, so the next group