2015/04/06

【UVa】714-Coping books (binary search,最大值最小化)




714 link

題目大意
input是書的數量m,抄錄者數量k,和每本書的頁數。
每一個抄錄者要分配到整數量的書,每一個人的分配到的頁數要最平均。
每一個人分配到的書要相鄰。

解題思路
這是一個最大值最小化的題目,也就是說在所有可能中,這些人裡面分到最多頁數的那個人得到的要是最小的可能。
標準解法是用DP,這邊我用Binary Search,找的是最小的可能頁數。
check()函式是分書,從最後一本開始分起,如果加上下一本書會>mid,則切斷,注意要算分成幾等份,e.g 3個人只能切兩次。


Code
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
int m,k;
int p[501];
long long int mid, upper_bound, lower_bound;
int check(){
    int i, part_count = 0;
    long long int tmp = 0;
    for (i = m-1; i >= 0; i--) {
        if (tmp+p[i] > mid){
            if (part_count==k-1)
                return 2;
            tmp = p[i];
            part_count++;
        }
        else
            tmp += p[i];
    }
    return 3;
}
void output(){
    int i, j, count=0;
    long long int tmp=0, index=0;
    int cut[501];
    for (i = 0; i < 501; i++) {
        cut[i] = 0;
    }
    for (i = m-1; i >= 0; i--) {
        if (tmp+p[i] > upper_bound || k-count-1 > i) {
            tmp = p[i];
            count++;
            cut[index++] = i;
        }
        else
            tmp += p[i];
    }
    for(i = 0;i < m-1;i++)
    {
        printf("%d ",p[i]);
        for(j=0;j<index;j++)
            if(i==cut[j]){
                printf("/");
                printf(" ");
            }
    }
    printf("%d\n",p[m-1]);
}
int main(int argc, const char * argv[]) {
    int N, i, j;
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d %d",&m,&k);
        upper_bound = 0;
        lower_bound = 0;
        for (j = 0; j < m; j++) {
            scanf("%d",&p[j]);
            if (p[j] > lower_bound) lower_bound=p[j];
            upper_bound += p[j];
        }
        while (upper_bound>lower_bound) {
            mid = (lower_bound+upper_bound)/2;
            if (check()==2)
                lower_bound = mid+1;
            else
                upper_bound = mid;
        }
        output();
         
    }
     
    return 0;
}