C++에서 Q번째 사람의 최대 막대 길이

문제 설명

배열에서 n개의 막대 길이가 주어집니다. 누군가가 막대를 선택하면 가장 긴 막대의 절반(또는 (최대 + 1) / 2 )을 할당하고 나머지 부분(최대 – 1) / 2를 다시 넣습니다. 충분한 수의 막대가 항상 사용 가능하다고 가정할 수 있으며, qi가 1부터 시작하는 유효한 사람 번호인 경우 배열 q[]에 제공된 M 쿼리에 응답하여 qith 사람이 사용할 수 있는 최대 막대 길이를 찾습니다.

예시

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인 막대를 얻습니다.
• 그런 다음 배열에서 12를 제거하고 (12 – 1) / 2 =5를 다시 넣습니다.
• 두 번째 사람은 최대 길이가 10인 막대를 얻습니다.
• 그런 다음 다시 (10 – 1) / 2 =4
• 세 번째 사람은 최대 길이가 9인 막대를 얻습니다.

알고리즘

• 먼저 모든 길이를 정렬하고 스택에 푸시합니다.
• 스택의 맨 위 요소를 2로 나누고 나머지 길이를 대기열에 넣습니다.
• 스택이 비어 있으면 프론트 큐를 팝하고 큐로 다시 푸시합니다. 0이 아닌 경우 절반(앞면 / 2)입니다.
• 대기열이 비어 있으면 스택에서 꺼내 대기열로 푸시하고 0이 아니면 절반(상단 / 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