f607. 3. 切割費用 - 高中生程式解題系統

內容

有一根長度為 $L$ 的棍子，你會把這個棍子切割 $n$ 次。

假設一開始棍子左端放在數線上 $0$ 的位置，棍子的右端放在數線上 $L$ 的位置，每次的切割會給定一個介於 $0$ 到 $L$ 的數字表示要切個的位置，你要把穿過個這位置的棍子切成兩段，而所需的花費就等於所切割的棍子的長度。

輸入說明

第一行有兩個整數 $n, L$ 。

接下來 $n$ 行每行有兩個整數 $x, i$ ，表示 $x$ 位置被切過一刀，而這刀是全部的切割中的第 $i$ 刀，保證 $i$ 是介於 $[1, n]$ 的整數且不會重複。

配分

20分: $1 \leq n \leq 1000, 1 \leq L \leq 10^{7}$
30分: $1 \leq n \leq 50000, 1 \leq L \leq 10^{7}$
50分: $1 \leq n \leq 200000, 1 \leq L \leq 10^{7}$

輸出說明

輸出一個整數表示總共的切割費用，答案可能超過 $2^{31}$ 但不會超過 $2^{60}$ 。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 2.0s , <1M
公開測資點#1 (5%): 2.0s , <1M
公開測資點#2 (5%): 2.0s , <1M
公開測資點#3 (5%): 2.0s , <1M
公開測資點#4 (5%): 2.0s , <1M
公開測資點#5 (5%): 2.0s , <1M
公開測資點#6 (5%): 2.0s , <1M
公開測資點#7 (5%): 2.0s , <1M
公開測資點#8 (5%): 2.0s , <1M
公開測資點#9 (5%): 2.0s , <1M
公開測資點#10 (5%): 2.0s , <10M
公開測資點#11 (5%): 2.0s , <10M
公開測資點#12 (5%): 2.0s , <10M
公開測資點#13 (5%): 2.0s , <10M
公開測資點#14 (5%): 2.0s , <10M
公開測資點#15 (5%): 2.0s , <10M
公開測資點#16 (5%): 2.0s , <10M
公開測資點#17 (5%): 2.0s , <10M
公開測資點#18 (5%): 2.0s , <10M
公開測資點#19 (5%): 2.0s , <10M

提示：

標籤:

APCS

出處:

2021年1月 APCS [管理者： edison1998402@gmail.com

cthbst (吳宗達) ]

編號	身分	題目	主題	人氣	發表日期
44946	toseanlin@gm ... (Dr. SeanXD)	f607	C++詳解	91	2024-12-28 19:11
41247	glps1004@gma ... (Ian)	f607	簡單解法	335	2024-07-14 15:04
34576	luray0601@gm ... (QWERTYPIG)	f607	C++題解(含想法)	1128	2023-04-01 19:13
33848	asnewchien@g ... (david)	f607	Python 解題影片	538	2023-02-08 09:15
33527	a110608@ctes ... (鍾均)	f607	C++ Python 雙題解！(附完整解題過程&程式碼)	922	2023-01-11 21:03