1416 . 電梯水題
TopCoder
Tags
Description
今天有 $n$ 個人在百貨公司地下一樓美食街排隊，要坐電梯上樓。透過調查，我們知道隊伍從前頭數來第 $i$ 個人的體重是 $a_i$，和他要去的樓層是 $b_i$。大家都趕時間，所以會引起公憤的插隊是嚴格禁止的。
為了更有效率的上樓，這些人達成了共識：每個人都可以和一些隊伍中附近的人一起共乘，前提是單趟共乘的負重不能超過電梯的最大負重 $w$。每趟共乘會把一些隊伍裡的人送上樓，每到一個有人要下的樓層才會停；停完繼續上樓，一直到所有人都出電梯為止，再下來接下一趟共乘的客人。
每個人進電梯都帶著喜悅的心情，希望可以用最快速度到達目的地，但中途任何減速和停下都會誤到時間，十分令人不耐煩。所以我們把每個人到他的樓層之前，電梯共停了幾次，稱為他的生氣程度。
此外，為了避免有人等太多趟才坐到電梯，大家也決定了一個正整數 $k$，代表必須要在 $k$ 趟共乘以內，讓所有人都有坐到電梯。
我們的目標是安排共乘的班次，最小化所有人裡最生氣的人的生氣程度。請輸出該生氣程度。或是無法安排 $k$ 趟共乘都在負重 $w$ 以內，請輸出 $-1$。
Input Format
輸入的第一行是三個正整數 $n, k, w$。
第二行有 $n$ 個正整數 $a_1,\dots,a_n$。
第三行有 $n$ 個正整數 $b_1,\dots,b_n$。
- $1 \leq k \leq n \leq 5 \cdot 10^ 5$
- $1 \leq a_i \leq w \leq 10^ 9$
- $1 \leq b_i \leq n$
Output Format
輸出一行一個整數，代表能達到的最大生氣程度最小值。或是無法安排 $k$ 趟共乘都在負重 $w$ 以內，請輸出 $-1$。
Sample Input 1
5 2 16 4 8 7 6 3 1 2 3 4 5
Sample Output 1
2
Sample Input 2
5 2 14 4 8 7 6 3 5 4 3 2 1
Sample Output 2
-1
Sample Input 3
5 2 16 4 8 7 6 3 1 2 3 4 4
Sample Output 3
1
Sample Input 4
5 1 1000000000 4 8 7 6 3 1 2 3 4 5
Sample Output 4
4
Sample Input 5
5 5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 5 5 5 5 5
Sample Output 5
0
Hints
第三筆範例測資中，分別讓前兩個人和後三個人共乘的話，兩趟總重都可以在最大負重 16 以內。
此時最生氣的人（第 2, 4, 5 位）只有生氣程度 1，因為考慮各自的共乘，到他們的樓層前只有停過一次。
不管怎麼改變共乘的分配，我們都無法讓最生氣的人有再更低的生氣程度了，所以答案就是 1。
第一筆範例測資中，能達成最佳解的一種方案也是讓前兩個人和後三個人共乘。
第二筆範例測資中，不管我們怎麼安排，都無法在兩趟共乘內讓所有人都坐到電梯。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | 範例測資 | 0 |
| 2 | 5~27 | $b_1,\dots,b_n$ 皆相異，且 $n \leq 1000$ | 30 |
| 3 | 0~42 | $n \leq 1000$ | 25 |
| 4 | 0~57 | 無額外限制 | 45 |
| 5 | 0~72 | 賽後補強測資 | 0 |