Tuyên bố vấn đề
Cho trước độ dài của n thanh trong một mảng. Nếu bất kỳ người nào chọn bất kỳ thanh nào, một nửa của thanh dài nhất (hoặc (tối đa + 1) / 2) được chỉ định và phần còn lại (tối đa - 1) / 2 được đặt lại. Có thể giả định rằng luôn có đủ số lượng thanh, hãy trả lời M truy vấn được đưa ra trong mảng q [] để tìm chiều dài lớn nhất của thanh có sẵn cho qith người, với điều kiện qi là số người hợp lệ bắt đầu từ 1
Ví dụ
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. Nếu mảng đầu vào là {6, 5, 9, 10, 12} và
Mảng truy vấn là {1, 3} thì đầu ra sẽ là 12 và 9 là -
- Người đầu tiên nhận được thanh có chiều dài tối đa, tức là 12
- Sau đó, chúng tôi xóa 12 khỏi mảng và đặt lại (12 - 1) / 2 =5
- Người thứ hai nhận được thanh có chiều dài tối đa, tức là 10
- Sau đó, chúng tôi đặt lại (10 - 1) / 2 =4
- Người thứ ba nhận được thanh có chiều dài tối đa, tức là 9
Thuật toán
- Đầu tiên, hãy sắp xếp tất cả các độ dài và đẩy chúng vào một ngăn xếp
- Lấy phần tử trên cùng của ngăn xếp và chia cho 2 và đẩy chiều dài còn lại vào hàng đợi
- Nếu ngăn xếp trống, hãy bật hàng đợi phía trước và đẩy trở lại hàng đợi. Đó là một nửa (trước / 2), nếu khác 0
- Nếu hàng đợi trống, hãy bật từ ngăn xếp và đẩy đến hàng đợi đó là một nửa (trên cùng / 2), nếu khác 0
- Nếu cả hai đều không trống, hãy so sánh trên cùng và phía trước, cái nào lớn hơn sẽ được xuất hiện, chia cho 2 rồi đẩy lùi lại
- Dừng khi cả ngăn xếp và hàng đợi đều trống
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Rod length = 12 10 9 6 6 5 5 4 3 3