這題忍不住要寫個解題報告！

測資裡  n = 切點數  L = 棍子長度  ans = 0

1)  一開始的想法是有 n 個切點和刀序

一開始宣告一個 [0, L] 的陣列，

從第一刀開始切，第一刀切在 100 

則 ans = L - 0  陣列 --> [0, 100, L]

第二刀假設為 150 先找到 150 可以插入到哪個位置，

顯然 ans += L - 100 陣列 --> [0, 100, 150, L]

依序到第 n 刀，就是要做 n 次 insert

大部分的人會用 binary search 去找那個位置，

python 可以 import bisect 用 bisect 去找哪個位置比較省時間，

這樣能 AC 但也要 5sec，而標準的時間是3秒( python )。

2) 第二個想法是把切點做排序，

以 [2(cut2), 3(cut1), 5(cut3)] 為例，每一刀往左右找到刀序小的兩個切點即可。

這時我建議由 n downto 1 的刀序來找。

因為第 n 刀的左右兩點必然比第 n 刀還早存在，算完成本後再把第 n 刀的值抹去。

所以  [0, 2(cut2), 3(cut1), 5(cut3), 7] 

先找 cut3  ans = 7-3 = 4  -->  [0, 2(cut2), 3(cut1), 7]

再找 cut2  ans = 4 + (3-0) = 7 -->  [0, 3(cut1), 7]

再找 cut1  ans = 7 + (7-0) = 14 -->  [0, 7]

這樣每次抹去一個值要做一次 pop 的動作也是浪費時間。

底下是我的寫法

cut = {1: 3, 2: 2, 3: 5}  # key = 刀序  value = 切點

p = {0: [0,2], 2: [0,3], 3: [2,5], 5: [3,7], 7: [5,0]} 

# key = 排序後的切點 value = [left key, right key]

先找 cut3  cut3 = 5  ans = 7-3 = 4  -->  p = {0: [0,2], 2: [0,3], 3: [2,7], 5: [3,7], 7: [3,0]} 

再找 cut2  cut2 = 2  ans = 4 + (3-0) = 7 -->  p = {0: [0,3], 2: [0,3], 3: [0,7], 5: [3,7], 7: [3,0]} 

再找 cut1  cut2 = 1  ans = 7 + (7-0) = 14 -->  p = {0: [0,3], 2: [0,3], 3: [0,7], 5: [3,7], 7: [3,0]} 

做完每個點後，讓前後2個點手牽手。

請問哪裡還可以優化?

sum=0
import bisect
def binary(n):
    global sum
    bisect.insort_left(k,n)
    sum+=k[bisect.bisect_left(k,n)+1]-k[bisect.bisect_left(k,n)-1]
a,b=map(int,input().split(' '))
k=[0,b]
k1=[]
for i in range(a):
    m,n=map(int,input().split(' '))
    s=[m,n]
    k1.append(s)
k1.sort(key=lambda x:x[1])
for i in range(len(k1)):
    binary(k1[i][0])
print(sum)

感覺您寫的程式常在做虛功 ( 無意冒犯 )

改成這樣就過了，您知道為什麼嗎

v = bisect.bisect_left(k,n)

sum += k[v+1] - k[v-1]

 

請問大大為甚麼?

 

 

我懂了，您的意思是依我的寫法，須不斷地查找位置，倒不如先設一個變數存放紀錄，就會省去一次查找的時間，謝謝指教!