發表新討論
#31969: python NA:4% 求大神教教我怎麼改


nihscs109030 (Rain)

學校 : 不指定學校
編號 : 124564
來源 : [123.204.127.231]
最後登入時間 ：
2023-07-28 17:09:37
b966. 3. 線段覆蓋長度 -- 2016年3月apcs | From: [175.180.65.198] | 發表日期 : 2022-09-03 01:07

求大神教教我怎麼改

startAll, endAll = [], []
quantity = int(input())
while quantity != 0:
    start, end = map(int, input().split(" "))
    startAll.append(start)
    endAll.append(end)
    quantity -= 1

length = 0
start = min(startAll)
end = max(endAll)
for block in range(start+1, end):
    for head, tail in zip(startAll, endAll):
        if block >= head and block <= tail:
            length += 1
            break

print(length)

 

 
 

 

 
#31970: Re: python NA:4% 求大神教教我怎麼改


cges30901 (cges30901)

學校 : 不指定學校
編號 : 30877
來源 : [101.136.203.77]
最後登入時間 ：
2024-04-07 15:34:14
b966. 3. 線段覆蓋長度 -- 2016年3月apcs | From: [59.115.40.253] | 發表日期 : 2022-09-03 09:49
2.
for block in range(start+1, end):
        if block >= head and block <= tail:

 

 
 

 


1. 這種方法太沒有效率了，就算把錯誤改掉也只能70%後面TLE，建議的方法是先排序，然後用一層的for迴圈就好了

2. start+1改start，block <= tail改成block < tail

 
#31971: Re: python NA:4% 求大神教教我怎麼改


nihscs109030 (Rain)

學校 : 不指定學校
編號 : 124564
來源 : [123.204.127.231]
最後登入時間 ：
2023-07-28 17:09:37
b966. 3. 線段覆蓋長度 -- 2016年3月apcs | From: [175.180.65.198] | 發表日期 : 2022-09-03 10:07
2.
for block in range(start+1, end):
        if block >= head and block <= tail:

 

 
 

 


1. 這種方法太沒有效率了，就算把錯誤改掉也只能70%後面TLE，建議的方法是先排序，然後用一層的for迴圈就好了

2. start+1改start，block <= tail改成block < tail


還真的TLE，感謝！

 
#31977: Re: python NA:4% 求大神教教我怎麼改


nihscs109030 (Rain)

學校 : 不指定學校
編號 : 124564
來源 : [123.204.127.231]
最後登入時間 ：
2023-07-28 17:09:37
b966. 3. 線段覆蓋長度 -- 2016年3月apcs | From: [175.180.65.198] | 發表日期 : 2022-09-03 12:07

求大神教教我怎麼改

startAll, endAll = [], []
quantity = int(input())
while quantity != 0:
    start, end = map(int, input().split(" "))
    startAll.append(start)
    endAll.append(end)
    quantity -= 1

length = 0
start = min(startAll)
end = max(endAll)
for block in range(start+1, end):
    for head, tail in zip(startAll, endAll):
        if block >= head and block <= tail:
            length += 1
            break

print(length)

 

 
 

 

改過後的soultion

 

scope = []
quantity = int(input())
while quantity != 0:
    start, end = map(int, input().split(" "))
    scope.append((start, end))
    quantity -= 1

length = 0
scope.sort(key=lambda x: x[0])
start, end = scope[0][0], scope[0][1]
for head, tail in scope:
    if head > end:
        length += end - start
        start, end = head, tail
        continue

    if tail < end:
        pass
    else:
        end += tail - end
 
length += end - start
print(length)

 

 
ZeroJudge Forum