高中生程式解題系統

#35140: 為什麼會TLE? python

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.11.221]
最後登入時間：
2024-02-04 16:09:17

h028. 202001_3 砍樹 -- 2020年1月 APCS | From: [123.193.213.137] | 發表日期 : 2023-05-11 19:42

from sys import stdin

n,l=map(int,stdin.readline().split())

p=[0]+list(map(int,stdin.readline().split()))+[l]

h=list(map(int,stdin.readline().split()))

d=[0]*(n+1)

for i in range(n+1):d[i]=p[i+1]-p[i]

ans=0

maxh=0

i=n-1

while i>=0:

k=i

while True:

if k>=n:break

if h[k]<=d[k] or h[k]<=d[k+1]:

ans+=1

hi=h.pop(k)

if hi>maxh:maxh=hi

d[k]+=d.pop(k+1)

k-=1

n-=1

else:break

k+=1

i-=1

print(ans)

print(maxh)

| 回應文章 | 回原始文章

#35148: Re: 為什麼會TLE? python

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.11.221]
最後登入時間：
2024-02-04 16:09:17

h028. 202001_3 砍樹 -- 2020年1月 APCS | From: [59.124.229.253] | 發表日期 : 2023-05-12 12:04

from sys import stdin
n,l=map(int,stdin.readline().split())
on=n
p=[0]+list(map(int,stdin.readline().split()))+[l]
h=list(map(int,stdin.readline().split()))
d=[0]*(n+1)
for i in range(n+1):d[i]=p[i+1]-p[i]
maxh=0
for i in range(n-1,-1,-1):
while i<n:
if h[i]<=d[i] or h[i]<=d[i+1]:
hi=h.pop(i)
if hi>maxh:maxh=hi
d[i]+=d.pop(i+1)
n-=1
else:break
print(on-n)
print(maxh)

還是過不了

| 回應文章 | 回原始文章

#35161: Re: 為什麼會TLE? python

r1cky (hehe)

學校 : 國立臺灣師範大學
編號 : 158637
來源 : [140.122.136.123]
最後登入時間：
2024-04-25 13:42:09

h028. 202001_3 砍樹 -- 2020年1月 APCS | From: [1.34.88.173] | 發表日期 : 2023-05-13 16:53

from sys import stdin
n,l=map(int,stdin.readline().split())
on=n
p=[0]+list(map(int,stdin.readline().split()))+[l]
h=list(map(int,stdin.readline().split()))
d=[0]*(n+1)
for i in range(n+1):d[i]=p[i+1]-p[i]
maxh=0
for i in range(n-1,-1,-1):
while i if h[i]<=d[i] or h[i]<=d[i+1]:
hi=h.pop(i)
if hi>maxh:maxh=hi
d[i]+=d.pop(i+1)
n-=1
else:break
print(on-n)
print(maxh)

還是過不了

python list 的 pop() 方法的 time complexity 似乎為 $O(N)$(只有 pop 尾端是 $O(1)$)，所以這樣這段程式最差會是 $O(N^2)$，並不會通過，這代表必須得找個更好的策略。

關於 pop() 方法的 time complexity 可以看這篇討論 : 連結

| 回應文章 | 回原始文章

#35163: Re: 為什麼會TLE? python

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.11.221]
最後登入時間：
2024-02-04 16:09:17

h028. 202001_3 砍樹 -- 2020年1月 APCS | From: [123.193.213.137] | 發表日期 : 2023-05-13 19:33

from sys import stdin
n,l=map(int,stdin.readline().split())
on=n
p=[0]+list(map(int,stdin.readline().split()))+[l]
h=list(map(int,stdin.readline().split()))
d=[0]*(n+1)
for i in range(n+1):d[i]=p[i+1]-p[i]
maxh=0
for i in range(n-1,-1,-1):
while i if h[i]<=d[i] or h[i]<=d[i+1]:
hi=h.pop(i)
if hi>maxh:maxh=hi
d[i]+=d.pop(i+1)
n-=1
else:break
print(on-n)
print(maxh)

還是過不了

python list 的 pop() 方法的 time complexity 似乎為 $O(N)$(只有 pop 尾端是 $O(1)$)，所以這樣這段程式最差會是 $O(N^2)$，並不會通過，這代表必須得找個更好的策略。

關於 pop() 方法的 time complexity 可以看這篇討論 : 連結

謝謝，我再試試看其他方法

| 回應文章 | 回原始文章

#35173: Re: 為什麼會TLE? python

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.11.221]
最後登入時間：
2024-02-04 16:09:17

h028. 202001_3 砍樹 -- 2020年1月 APCS | From: [123.193.213.137] | 發表日期 : 2023-05-14 15:21

from sys import stdin
n,l=map(int,stdin.readline().split())
on=n
p=[0]+list(map(int,stdin.readline().split()))+[l]
h=list(map(int,stdin.readline().split()))
d=[0]*(n+1)
for i in range(n+1):d[i]=p[i+1]-p[i]
maxh=0
for i in range(n-1,-1,-1):
while i if h[i]<=d[i] or h[i]<=d[i+1]:
hi=h.pop(i)
if hi>maxh:maxh=hi
d[i]+=d.pop(i+1)
n-=1
else:break
print(on-n)
print(maxh)

還是過不了

python list 的 pop() 方法的 time complexity 似乎為 $O(N)$(只有 pop 尾端是 $O(1)$)，所以這樣這段程式最差會是 $O(N^2)$，並不會通過，這代表必須得找個更好的策略。

關於 pop() 方法的 time complexity 可以看這篇討論 : 連結

謝謝，我再試試看其他方法

我不使用pop 結果更慢了

from sys import stdin

n,l=map(int,stdin.readline().split());on=n

p=[0]+list(map(int,stdin.readline().split()))+[l]

h=list(map(int,stdin.readline().split()))

d=[p[i+1]-p[i] for i in range(n+1)]

ans=0

maxh=0

#print(h,"tree")

#print(d)

for i in range(n-1,-1,-1):

k=i

while k<n:

#print(k)

if h[k]==-1:k+=1;continue

if h[k]<=d[i] or h[k]<=d[k+1]:

#print(k,"2")

#print("-1",k+1,h[k],d[i],d[k+1])

if h[k]>maxh:maxh=h[k]

h[k]=-1;ans+=1

d[i]+=d[k+1]

d[k+1]=0

k+=1

else:break

#print(h,"tree")

#print(d)

print(ans)

print(maxh)

| 回應文章 | 回原始文章

#35260: Re: 為什麼會TLE? python

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.11.221]
最後登入時間：
2024-02-04 16:09:17

h028. 202001_3 砍樹 -- 2020年1月 APCS | From: [123.193.213.137] | 發表日期 : 2023-05-19 20:04

吐血弄了三個禮拜

要用雙向鏈結串列

不能不停地掃

每次砍掉樹回去看背後有沒有樹可以連鎖反應砍

def Del(idx):

global r

global l

li=l[idx];ri=r[idx]

if li!="E":r[li]=(ri if ri!="E" else "E")

if ri!="E":l[ri]=(li if li!="E" else "E")

from sys import stdin

n,L=map(int,stdin.readline().split())

p=[0 ]+[int(i) for i in stdin.readline().split()]+[L ]

h=[10**9]+[int(i) for i in stdin.readline().split()]+[10**9]

r=[(i+1 if i!=n+1 else "E") for i in range(n+2)]

l=[(i-1 if i!=0 else "E") for i in range(n+2)]

ans=0;maxh=0

'''while True:

run=True

i=0

while i!="E":

i=r[i]

if i=="E":break

hi=h[i]

try:

if p[r[i]]-p[i]>=hi:

if hi>maxh:maxh=hi

Del(i)

run=False

ans+=1

continue

except:pass

try:

if p[i]-p[l[i]]>=hi:

if hi>maxh:maxh=hi

Del(i)

run=False

ans+=1

except:pass

if run:break TLE60%'''

i=0

while True:

i=r[i]

if i=="E":break

k=r[i]

while k!="E":

k=l[k]

if k=="E":break

hi=h[k]

if r[k]!="E":

if p[r[k]]-p[k]>=hi:

if hi>maxh:maxh=hi

Del(k)

ans+=1

continue

if l[k]!="E":

if p[k]-p[l[k]]>=hi:

if hi>maxh:maxh=hi

Del(k)

ans+=1

continue

break

print(ans)

print(maxh)

| 回應文章 | 回原始文章

ZeroJudge Forum