คำชี้แจงปัญหา
กำหนดความยาวของ n แท่งในอาร์เรย์ หากมีคนหยิบไม้เท้าใด ๆ ครึ่งหนึ่งของคันที่ยาวที่สุด (หรือ (สูงสุด + 1) / 2 ) จะถูกกำหนดและส่วนที่เหลือ (สูงสุด – 1) / 2 จะถูกนำกลับ อาจสันนิษฐานได้ว่ามีจำนวนแท่งไม้เพียงพออยู่เสมอ ตอบคำถาม M ที่ให้ไว้ในอาร์เรย์ q[] เพื่อค้นหาความยาวของแท่งไม้ที่ใหญ่ที่สุดสำหรับบุคคลที่ qith โดยที่ qi เป็นหมายเลขบุคคลที่ถูกต้องโดยเริ่มตั้งแต่ 1
ตัวอย่าง
Input : a[] = {6, 5, 9, 10, 12}
q[] = {1, 3}
Output : 12 9
The first person gets maximum length as 12.
We remove 12 from array and put back (12 -1) / 2 = 5.
Second person gets maximum length as 10.
We put back (10 - 1)/2 which is 4.
Third person gets maximum length as 9. หากอาร์เรย์อินพุตคือ {6, 5, 9, 10, 12} และ
คิวรี่อาร์เรย์คือ {1, 3} ดังนั้นเอาต์พุตจะเป็น 12 และ 9 เป็น −
- คนแรกได้รับไม้เท้าที่มีความยาวสูงสุดคือ 12
- จากนั้นเราลบ 12 ออกจากอาร์เรย์แล้วใส่กลับ (12 – 1) / 2 =5
- คนที่ 2 โดนไม้เรียวที่มีความยาวสูงสุด 10
- จากนั้นเราก็ใส่กลับ (10 – 1) / 2 =4
- บุคคลที่สามได้รับไม้เรียวที่มีความยาวสูงสุดคือ 9
อัลกอริทึม
- ขั้นแรกให้เรียงความยาวทั้งหมดแล้วดันเข้าที่กอง
- นำองค์ประกอบบนสุดของสแต็กแล้วหารด้วย 2 แล้วดันความยาวที่เหลือไปที่คิว
- หากสแต็กว่างเปล่า ให้เปิดคิวด้านหน้าและกดกลับไปที่คิว ครึ่งหนึ่ง (หน้า / 2) ถ้าไม่ใช่ศูนย์
- หากคิวว่าง ให้เปิดจากสแต็กแล้วกดไปที่คิว จะเป็นครึ่ง (บนสุด / 2) หากไม่ใช่ศูนย์
- หากทั้งคู่ไม่ว่าง ให้เปรียบเทียบด้านบนและด้านหน้า อันไหนใหญ่กว่าก็ให้แตก หารด้วย 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
