คำอธิบายปัญหา
กำหนดความยาวของไม้ n ไม้ในอาร์เรย์ ถ้าคนคนใดคนหนึ่งเลือกไม้ไหนก็ตาม ครึ่งหนึ่งของไม้ที่ยาวที่สุด (หรือ (max + 1) / 2) จะถูกมอบให้ และส่วนที่เหลือ (max – 1) / 2 จะถูกนำกลับไปใส่ สามารถสมมติได้ว่ามีไม้เพียงพอเสมอ ตอบคำถาม M คำถามที่ให้มาในอาร์เรย์ q[] เพื่อหาความยาวไม้ที่ใหญ่ที่สุดที่มีอยู่สำหรับคนที่ qi โดยที่ qi เป็นหมายเลขคนที่ถูกต้องเริ่มจาก 1
ตัวอย่าง
Input : a[] = {6, 5, 9, 10, 12} q[] = {1, 3} Output : 12 9 คนแรกได้ความยาวสูงสุด 12 นำ 12 ออกจากอาร์เรย์และใส่กลับ (12 -1) / 2 = 5 คนที่สองได้ความยาวสูงสุด 10 ใส่กลับ (10 - 1)/2 = 4 คนที่สามได้ความยาวสูงสุด 9ถ้าอาร์เรย์นำเข้าคือ {6, 5, 9, 10, 12} และ
อาร์เรย์คำถามคือ {1, 3} ผลลัพธ์จะเป็น 12 และ 9 ดังนี้:
- คนแรกได้ไม้ที่มีความยาวสูงสุดคือ 12
- จากนั้นนำ 12 ออกจากอาร์เรย์และใส่กลับ (12 – 1) / 2 = 5
- คนที่สองได้ไม้ที่มีความยาวสูงสุดคือ 10
- จากนั้นใส่กลับ (10 – 1) / 2 = 4
- คนที่สามได้ไม้ที่มีความยาวสูงสุดคือ 9
อัลกอริทึม
- เรียงลำดับความยาวทั้งหมดและนำเข้าไปในสแต็ก (stack)
- นำองค์ประกอบบนสุดของสแต็ก หาร 2 และนำความยาวที่เหลือเข้าคิว (queue)
- ถ้าสแต็กว่าง ให้ดึงหน้าคิวและนำกลับเข้าไปในคิว ครึ่งหนึ่ง (front / 2) ถ้าไม่เป็นศูนย์
- ถ้าคิวว่าง ให้ดึงจากสแต็กและนำเข้าไปในคิว ครึ่งหนึ่ง (top / 2) ถ้าไม่เป็นศูนย์
- ถ้าทั้งสองไม่ว่าง ให้เปรียบเทียบ top และ front ตัวไหนใหญ่กว่า ให้ดึงตัวนั้นออก หาร 2 แล้วนำกลับเข้าไป
- หยุดเมื่อทั้งสแต็กและคิวว่างเปล่า
ตัวอย่างโค้ด
#include <bits/stdc++.h> using namespace std; vector<int> getMaxRodLength(int *arr, int n, int m) { queue<int> q; sort(arr, arr + n); stack<int> s; for (int i = 0; i < n; ++i) { s.push(arr[i]); } vector<int> result; while (!s.empty() || !q.empty()) { int val; if (q.empty()) { val = s.top(); result.push_back(val); s.pop(); val = val / 2; if (val) { q.push(val); } } else if (s.empty()) { val = q.front(); result.push_back(val); q.pop(); val = val / 2; if (val != 0) { q.push(val); } } else { val = s.top(); int fr = q.front(); if (fr > val) { result.push_back(fr); q.pop(); fr = fr / 2; if (fr) { q.push(fr); } } else { result.push_back(val); s.pop(); val = val / 2; if (val) { q.push(val); } } } } return result; } int main() { int rods = 5; int queries = 10; int arr[rods] = {6, 5, 9, 10, 12}; vector<int> result = getMaxRodLength(arr, rods, queries); int query[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int n_query = sizeof(query) / sizeof(query[0]); cout << "Rod length = "; for (int i = 0; i < n_query; ++i) { cout << result[query[i] - 1] << " "; } cout << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้:
Rod length = 12 10 9 6 6 5 5 4 3 3
