資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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
更新於：2020年1月10日
118 次瀏覽
廣告