给定数组中n个杆的长度。如果有人捡起任何一根杆,则会分配最长杆的一半(或(max + 1)/ 2),其余部分(最大– 1)/ 2放回去。可以假设始终有足够数量的杆,如果qi是从1开始的有效人数,则回答数组q []中给出的M个查询以找到第q个人可用的杆的最大长度。
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,然后将剩余长度推入队列
如果堆栈为空,则弹出前队列并推回队列。如果不是零,则为一半(前/ 2)
如果队列为空,则从堆栈弹出并推送到队列的一半(顶部/ 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