ตรวจสอบว่าทุกคนสามารถโหวตสองเครื่องใน Python . ได้หรือไม่

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

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• total_sum :=ผลรวมขององค์ประกอบทั้งหมดของเวลา
• ถ้า total_sum <=x แล้ว
  • คืนค่า True
• เรียงลำดับเวลาของรายการ
• prev_sum :=อาร์เรย์ที่มีขนาดเท่ากับเวลาและเติมด้วย 0
• prev_sum[0] :=เวลา[0]
• สำหรับ i ในช่วง 1 ถึงขนาดของ prev_sum ให้ทำ
  • prev_sum[i] :=prev_sum[i - 1] + เวลา[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
• คืนค่าเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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