看到題目就知道要用貪心,因為我們要一直找體重最接近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)
Leave a Reply