โปรแกรมออกแบบคิวที่ย้ายสมาชิกที่ใช้ล่าสุดไปท้ายคิวใน Python

ออกแบบคิวเริ่มต้น 1..n มีฟังก์ชัน solve(k) ย้ายค่าที่ตำแหน่ง k ไปท้ายคิว และคืนค่าที่อยู่ท้ายคิวหลังย้าย

ตัวอย่าง: n=5, เรียก solve(5), solve(2), solve(3), solve(1) ผลลัพธ์ 5,2,4,1

วิธีแก้ปัญหา (Square Root Decomposition)

1. แบ่งข้อมูลเป็นบล็อกขนาด sqrt(n)
2. เก็บ data (ลิสต์ของบล็อก) และ index (ตำแหน่งเริ่มต้นของแต่ละบล็อก)
3. solve(k):
   • หาบล็อก i ที่มี k ด้วย bisect_right
   • ดึงค่า x ออกจากบล็อก
   • ปรับ index ของบล็อกถัดไป
   • ถ้าบล็อกสุดท้ายเต็ม ให้สร้างบล็อกใหม่
   • เพิ่ม x ไปท้าย
   • ถ้าบล็อก i ว่าง ให้ลบออก
   • คืน x

ตัวอย่างโค้ด

from bisect import bisect_right
from math import sqrt

class TestQueue:
    def __init__(self, n):
        self.n = n
        self.nn = int(sqrt(n))
        self.data = []
        self.index = []
        for i in range(1, n+1):
            ii = (i-1)//self.nn
            if ii == len(self.data):
                self.data.append([])
                self.index.append(i)
            self.data[-1].append(i)
    def solve(self, k):
        i = bisect_right(self.index, k) - 1
        x = self.data[i].pop(k - self.index[i])
        for ii in range(i+1, len(self.index)):
            self.index[ii] -= 1
        if len(self.data[-1]) >= self.nn:
            self.data.append([])
            self.index.append(self.n)
        self.data[-1].append(x)
        if not self.data[i]:
            self.data.pop(i)
            self.index.pop(i)
        return x

queue = TestQueue(5)
print(queue.solve(5))
print(queue.solve(2))
print(queue.solve(3))
print(queue.solve(1))

อินพุต

queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))

เอาต์พุต

5 2 4 1