โปรแกรมหาจำนวนการดำเนินการน้อยที่สุดย้ายลูกบอลไปแต่ละกล่องใน Python

สมมติว่าเรามีสตริงไบนารีชื่อ boxes โดย boxes[i] เป็น '0' หมายถึงกล่องที่ i ว่าง และ '1' หมายถึงมีลูกบอลหนึ่งลูก ตอนนี้ในหนึ่งการดำเนินการ เราสามารถย้ายลูกบอลหนึ่งลูกจากกล่องหนึ่งไปกล่องติดกัน หลังจากนั้นอาจมีลูกบอลมากกว่าหนึ่งลูกในบางกล่อง เราต้องหาอาร์เรย์ answer ขนาด n โดยที่ answer[i] คือจำนวนการดำเนินการน้อยที่สุดที่ต้องใช้เพื่อย้ายลูกบอลทั้งหมดไปกล่องที่ i

เช่น ถ้าอินพุตคือ boxes = "1101" ผลลัพธ์จะเป็น [4, 3, 4, 5]

• วางลูกบอลทั้งหมดที่กล่องแรก: เอาจากกล่อง 2 ใช้ 1 ครั้ง และจากกล่องสุดท้าย 3 ครั้ง รวม 4
• วางที่กล่องสอง: จากกล่อง 1 ใช้ 1 ครั้ง จากกล่องสุดท้าย 2 ครั้ง รวม 3
• วางที่กล่องสาม: จากกล่อง 2 และสุดท้าย 1 ครั้งแต่ละอัน จากกล่อง 1 ใช้ 2 ครั้ง รวม 4
• วางที่กล่องสุดท้าย: จากกล่อง 1 ใช้ 3 ครั้ง จากกล่อง 2 ใช้ 2 ครั้ง รวม 5

วิธีแก้ปัญหา

• left := 0, right := 0, dist := 0
• สำหรับ i ในช่วง 0 ถึงขนาดของ boxes - 1:
  • ถ้า boxes[i] เท่ากับ "1":
    • dist := dist + i
    • ถ้า i เท่ากับ 0: left := left + 1
    • มิฉะนั้น: right := right + 1
• arr := รายการ ใส่ dist เริ่มต้น
• สำหรับ i ในช่วง 1 ถึงขนาดของ boxes - 1:
  • แทรก arr[i-1] + left - right ลงท้าย arr
  • ถ้า boxes[i] เท่ากับ "1": left := left + 1, right := right - 1
• return arr

ตัวอย่าง

def solve(boxes):
    left = 0
    right = 0
    dist = 0
    for i in range(len(boxes)):
        if boxes[i] == "1":
            dist += i
            if i == 0:
                left += 1
            else:
                right += 1
    arr = [dist]
    for i in range(1, len(boxes)):
        arr.append(arr[i-1] + left - right)
        if boxes[i] == "1":
            left += 1
            right -= 1
    return arr

boxes = "1101"
print(solve(boxes))

อินพุต

"1101"

เอาต์พุต

[4, 3, 4, 5]