C++中第Q个人的最大木棍长度
问题陈述
给定一个数组中n根木棍的长度。如果任何人选择任何一根木棍,则分配最长木棍的一半(或 (max + 1) / 2),并将剩余部分 (max – 1) / 2 放回。可以假设始终有足够的木棍可用,回答数组q[]中给出的M个查询,以找到第q个人的最大可用木棍长度,前提是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
- 第二个人得到长度最长的木棍,即 10
- 然后我们放回 (10 – 1) / 2 = 4
- 第三个人得到长度最长的木棍,即 9
算法
- 首先对所有长度进行排序并将它们压入堆栈。
- 取堆栈的顶部元素,除以 2,并将剩余长度压入队列。
- 如果堆栈为空,则弹出队列的头部并压回队列。如果非零,则为其一半 (front / 2)。
- 如果队列为空,则从堆栈中弹出并压入队列,如果非零,则为其一半 (top / 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
广告