UVa 714

From Algorithmist
Jump to navigation Jump to search

714 - Copying Books[edit]

Summary[edit]

Use binary search, with some cleaning up for ties.

Better after UVa 11413

Explanation[edit]

Do a binary search on the maximum number of pages assigned to a scriber. You can easily test if a number is high enough by greedily assigning books to scribers. Once you have the optimal value, be sure to assign books to meet the tie-breaking rule (this is done greedily).

Another approach is dynamic programming, as long as you "fix" your solution to meet the tie-breaker requirement (or maybe assign books backwards?).

Gotcha's[edit]

  • Overflow should be a consideration (500 * 10000000 > 2^32)

Input[edit]

8
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
4 2
1 2 4 8
6 2
1 2 4 8 4 2
6 2
1 2 3 3 2 1
2 2
10000000 10000000
6 3
1000000 1 1 1 1 1
6 6
6 5 4 3 2 1

Output[edit]

100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100
1 2 4 / 8
1 2 4 / 8 4 2
1 2 3 / 3 2 1
10000000 / 10000000
1000000 / 1 / 1 1 1 1
6 / 5 / 4 / 3 / 2 / 1