2380 . 電梯難題
TopCoder
Tags
Description
在西元 2100 年時，舊的自強樓終於不堪重負倒塌了，因此蓋了新的自強樓，叫做新自強樓。新自強樓共有 $10^ 9 + 1$ 層樓，分別為第 $0$ 樓到第 $10 ^ 9$ 樓。由於有這麼多樓層，因此超級好心的校長在新自強樓設了 $k$ 臺電梯。$k$ 在正常的時候應為 $2$，但有時候電梯需要整修，會導致 $k$ 變成 $1$。由於課表是固定的，所以上下電梯的人也是固定的：每天的一開始，兩臺電梯會都停在第 $0$ 樓。接下來，總共會有 $n$ 組學生要上下電梯，其中第 $i$ 組學生要從第 $s_i$ 樓到第 $e_i$ 樓。這些學生會照順序使用電梯，而當他們要搭電梯時，其中一台電梯需要到 $s_i$ 樓載他們到 $e_i$ 樓。
俗話說：電梯之初，性本懶。電梯們希望他們移動的樓層數量越少越好（如果從第 $a$ 樓移到第 $b$ 樓，則代表電梯們移動了 $|a-b|$ 層樓。），但是他們不知道該怎麼分配工作才能達成他們的目標。請你寫一個程式，給定學生使用電梯的時程，幫電梯們最小化他們加起來移動的樓層數量，並輸出此答案。
Input Format
第一行有兩個正整數 $k,n$，代表電梯的數量跟接下來要搭乘電梯的人數
接下來 $n$ 行中每行有兩個正整數 $s_i,e_i$，代表第 $i$ 組學生要從第 $s_i$ 樓搭到第 $e_i$ 樓
對於所有測試資料：
- $1 \leq k \leq 2$
- $1 \leq n \leq 3 \cdot 10 ^ 5$
- $1 \leq s_i, e_i \leq 10 ^ 9$
- $s_i \neq e_i$
Output Format
請輸出一個整數，代表所有電梯加起來最少需要移動幾個樓層才能滿足所有學生的要求。
Sample Input 1
1 4
1 4
8 2
Sample Output 1
Sample Input 2
1 4
1 4
8 2
Sample Output 2
Sample Input 3
5 2
8 3
8 2
8 10
9 6
3 2
8 4
5 8
5 6
2 4
Sample Output 3
Hints
範例測資 1 解釋：只有一臺電梯，它會依序經過 $0 \rightarrow 1 \rightarrow 4 \rightarrow 1 \rightarrow 4 \rightarrow 8 \rightarrow 2$，總共經過 $|1-0|+|4-1|+|1-4|+|4-1|+|8-4|+|2-8|=20$ 層樓
範例測資 2 解釋：如果多了一臺電梯，可以把第一組學生分給電梯 1 ，把第二、三組學生分給電梯 2，如此一來電梯 1 需要走 $4$ 層樓，電梯 2 需要走 $14$ 層樓，加起來共 $18$ 層樓
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0, 3~9, 15~16, 25~26 | $k=1$ | 9 |
| 3 | 0~2, 8~14, 38 | $n \leq 20$ | 13 |
| 4 | 0~2, 8~24, 38 | $n \leq 5000$ | 27 |
| 5 | 0~38 | 無其他限制 | 51 |