看到題目就知道要用貪心,因為我們要一直找體重最接近x的人來湊, 除非>x,否則ans+=1。

除了貪心,還可以用雙指標–頭尾往中間,但是為什麼?

假設現在有一個小到大排序好list,因為一個車廂可以載最多2人,所以我們可以考慮把 “最重(right)跟最輕(left)” 放在同一車廂,盡可能的在 right-left <= x 的情況下接近x。

n,x  = map(int,input().split())
li = sorted(list(map(int,input().split())))
left = ans = 0
right = n-1
while left<=right:
    if li[right]+li[left]<=x:
        ans+=1
        left+=1
        right-=1
    else:# 太重,無他人匹配
        right-=1
        ans+=1 # 自己一個車廂

print(ans)


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *