ตรวจสอบว่าทุกคนสามารถลงคะแนนเสียงบนเครื่องจักรสองเครื่องได้หรือไม่ใน Python

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

เช่น ถ้าอินพุตเป็น n = 3, x = 7, time = [3, 5, 3] ผลลัพธ์จะเป็น True เนื่องจากที่เวลา t0 คนที่ 0 ไปที่เครื่องแรก และคนที่ 1 ไปที่เครื่องที่สอง ตอนเวลา t3 เครื่องแรกว่าง คนที่ 2 ไปที่เครื่องแรก และที่เวลา t5 เครื่องที่สองว่าง และที่เวลา t6 เครื่องแรกว่าง ดังนั้นผู้เข้าร่วมทุกคนโหวตเสร็จทันเวลา

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:

• total_sum := ผลรวมของทุกองค์ประกอบใน time
• ถ้า total_sum <= x แล้ว
  • คืนค่า True
• เรียงลำดับรายการ time
• prev_sum := อาร์เรย์ขนาดเท่ากับ time และเติมด้วย 0
• prev_sum[0] := time[0]
• สำหรับ i ในช่วง 1 ถึงขนาดของ prev_sum ทำ
  • prev_sum[i] := prev_sum[i - 1] + time[i]
• สำหรับ i ในช่วง 0 ถึงขนาดของ prev_sum ทำ
  • สำหรับ j ในช่วง i + 1 ถึงขนาดของ prev_sum - 1 ทำ
    • temp_sum := prev_sum[i] + (total_sum - prev_sum[j])
    • ถ้า temp_sum <= x และ total_sum - temp_sum <= x แล้ว
      • คืนค่า True
• คืนค่า False

ลองดูการนำไปใช้ดังต่อไปนี้เพื่อเข้าใจได้ดียิ่งขึ้น:

ตัวอย่าง

def solve(n, x, time):
    total_sum = sum(time)
    if total_sum <= x:
        return True
    time.sort()
    prev_sum = [0 for i in range(len(time))]
    prev_sum[0] = time[0]
    for i in range(1, len(prev_sum)):
        prev_sum[i] = prev_sum[i - 1] + time[i]
    for i in range(0, len(prev_sum)):
        for j in range(i + 1, len(prev_sum)):
            temp_sum = (prev_sum[i] + (total_sum - prev_sum[j]))
            if temp_sum <= x and total_sum - temp_sum <= x:
                return True
    return False

n = 3
x = 7
time = [3, 5, 3]
print(solve(n, x, time))

อินพุต

3, 7, [3, 5, 3]

ผลลัพธ์

True