python 題目求指點

45 回覆
2 Like 4 Dislike
2019-02-21 23:55:34
好 唔該哂巴打
2019-02-21 23:56:38
到你自己錯但又唔知錯咩真係唔慌唔好玩
2019-02-22 01:20:23
自己睇啦,大概係咁,留左comment
import random
import math
N,J,H=100000, 100, 1000000
#N,J,H = 18, 4, 100
arr = list(sorted([random.randint(1,H) for i in range(0,N)]))
#arr = [8, 16, 22, 26, 29, 32, 39, 50, 51, 54, 56, 59, 60, 64, 64, 65, 71, 77]
def canJump(arr, N, S):
    steps, start = 0, 0
    print("S:",S)
    for i in range(1,N):
        if (i-start <= S and arr[i]-arr[start] <= S):
            continue
        else: #Exceed the strength, we can only go to the previous element, so start = i-1
            steps += 1
            start = i-1
            if (steps == J and start < N - 1): # if steps == J, but we still don't reach the end
                print(S, "is not OK at ", i)
                return False
    return True

def jumper(arr, N, J):
    maxDiff = max([arr[i]-arr[i-1] for i in range(1,N)])
    start, end = max(maxDiff, math.ceil(N/J)), N
    print("start,end:",start, end)
    while (start < end):
        mid = start + (end - start) // 2
        if (canJump(arr, N, mid)):
            end = mid
        else:
            start = mid+1
    return start

print("result:",jumper(arr, N, J))
2019-02-22 01:32:43
A bug in the previous code
import random
import math
#N,J,H=100000, 100, 1000000
N,J,H = 18, 4, 100
#arr = list(sorted([random.randint(1,H) for i in range(0,N)]))
arr = [8, 16, 22, 26, 29, 32, 39, 50, 51, 54, 56, 59, 60, 64, 64, 65, 71, 77]
def canJump(arr, N, S):
    steps, start = 0, 0
    #print("S:",S)
    for i in range(1,N):
        if (i-start <= S and arr[i]-arr[start] <= S):
            continue
        else: #Exceed the strength, we can only go to the previous element, so start = i-1
            steps += 1
            start = i-1
            if (steps == J and start < N - 1): # if steps == J, but we still don't reach the end
                #print(S, "is not OK at ", i)
                return False
    return True

def jumper(arr, N, J):
    maxDiff = max([arr[i]-arr[i-1] for i in range(1,N)])
    start, end = max(maxDiff, math.ceil(N/J)), max(N, H)
    print("start,end:",start, end)
    while (start < end):
        mid = start + (end - start) // 2
        if (canJump(arr, N, mid)):
            end = mid
        else:
            start = mid+1
    return start

print("result:",jumper(arr, N, J))
2019-02-22 02:02:56
我想問下 S 同 H 分別代表左D 咩野?
2019-02-22 02:04:02
strength 同埋 highest height of the pillar?
2019-02-22 02:18:14
btw 巴打我之前runtime error 個d case 都搞點哂

但係有一個wrong answer
2019-02-22 04:44:44
ICPC
2019-02-22 08:07:52
係呀,highest height of pillar 其實應該要loop 一次條array 去搵,你改改佢
2019-02-22 08:21:28
我直接搵左最尾個element of array 做個 h

唔該哂師兄
btw 想問下你係咩background 覺得你打d code 好工整
2019-02-22 08:26:03
可能係boundary error
start, end = max(maxDiff, math.ceil(N-1/J)), max(N, H)
1,2,3,4,5 #N=5, J=2
S=2 就okay, 但之前math.ceil(N/J)),變左output 3
2019-02-22 08:32:35
係喎,已經sort 左,最後即係最大,咁okay la
你都可以咁工整既
我ust cs grad 左好耐啦
2019-02-22 08:50:19
兩年前學過少少c 放低左兩年 而家岩岩先開始學python 好多時見到條題目係諗到點樣做但自己唔識用program/algorithm 好有組織咁表達返出黎

師兄咁你而家撈咩 都係係cs industry 定係入左bank 做back office?
2019-02-22 09:03:12
做緊bank
你改左math.ceil 由N/J 去math.ceil((N-1)/J)
Can fix the problem?
2019-02-22 09:06:10
即係呢句,呢個N-1 我漏左括弧
應該係咁
start, end = max(maxDiff, math.ceil((N-1)/J)), max(N, arr[-1])
2019-02-23 00:37:28
搞點左了 唔該ching


btw 巴打其實我唔係好明steps 個到係做緊d 咩 其他部份都明
2019-02-23 08:05:18
if (i-start <= S and arr[i]-arr[start] <= S):
continue
i-start<=S 即係行既距離,另外係高度距離,如果match 到上面既condition, 即係行到,無事發生


else: #Exceed the strength, we can only go to the previous element, so start = i-1
steps += 1
start = i-1
if (steps == J and start < N - 1): # if steps == J, but we still don't reach the end
#print(S, "is not OK at ", i)
return False
return True

Match 唔到啦喎,即係我呢一steps 跳完,跳到去上一pillar就要停,咁steps 要加1,同時下次起步就要由上一pillar 開始,所以start=i-1

咁步數用哂(即係steps>J),但未到終點(start<N-1),即係跳唔完,return False

Example:
J=3, S=6
arr=[1,4,7,12,13,14,15,16,17,18,18,18]
由1 開始,if s=6, 1 to 7, 7 to 13, 13 to 2nd 18 (因為最多去到6格)
3 步只跳到去尾2,即係failed to jump
如果J=4 就okay
2019-02-23 08:06:36
步數用哂(steps==J)
2019-02-25 13:46:04
樓豬 Genius
吹水台自選台熱 門最 新手機台時事台政事台World體育台娛樂台動漫台Apps台遊戲台影視台講故台健康台感情台家庭台潮流台美容台上班台財經台房屋台飲食台旅遊台學術台校園台汽車台音樂台創意台硬件台電器台攝影台玩具台寵物台軟件台活動台電訊台直播台站務台黑 洞