你有很長很長的竹棒,總共有 $m$ 個竹節,因為這個竹子得了新型冠狀病毒,導致每一個竹節都一樣長。
小明是個很可惡的小屁孩,打 LOL 掛機、動嘴不動腦、罵人學店仔,這個大壞蛋對你的竹棒做了壞壞的事情,他拿打洞機在你的竹節上面打洞,你快要氣瘋了。
十分喜愛棒棒的你,決定用膠帶修復竹子,只要將膠帶貼上竹子表面就算修復完成,就算沒有被打洞的竹節也可以被貼膠帶。
小明總共傷害棒棒共 $n$ 個竹節,但是你只想用至多 $k$ 段膠帶修復棒棒,請問最少要使用多長的的膠帶才能修復這根棒棒?
竹棒總共有 $m$ 節,從 $1$ 開始編號到 $m$ 。
P.S. 每段膠帶長度可任意。
第一行有三個整數 $n, m$, $k$ ($1\leq n\leq10^ 5, n\leq m\leq10^ 9, 1\leq k\leq n$) 分別代表被破壞的竹節個數、全部的竹節數量以及至多使用的膠帶段數。
第二行有 $n$ 個整數 ($b_1,b_2,\cdots,b_n$) ,代表被破壞的竹節是第幾節,且依序由小到大。($1\leq b_i\leq m, b_1<b_2<\cdots<b_n$)
最短需要使用的膠帶總長度,單位為「竹節長」。
對於第一個範例,你會使用 $17$ 個竹節長的膠帶,分別貼在 $20\sim30$ ( $11$ 竹節長)之間與 $75\sim80$ ( $6$ 竹節長)之間。
對於第二個範例,你會使用 $6$ 個竹節長的膠帶,分別貼在 $1\sim4,60,87$ 。
No. | Testdata Range | Score |
---|---|---|
1 | 0~9 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 |