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;} |
