C++의 회전문

요청 목록이 있다고 가정합니다. 여기서 requests[i]에는 시간 t에 사람이 도착하여 안으로 들어가고(내부는 1을 사용함을 나타냄) 외부로 나가기를 원함(outside는 표시 0).

그래서 문이 하나뿐이고 문을 사용하는 데 한 시간 단위가 걸린다면 따라야 할 몇 가지 규칙이 있습니다 -

• 문은 'in' 위치에서 시작하여 마지막 참가자가 사용한 위치로 설정됩니다.

• 주어진 시간 t에 문에 참가자가 한 명만 있으면 문을 사용할 수 있습니다.

• 2인 이상 입장을 원할 경우 먼저 입장한 사람이 먼저 입장하고 이전에 사용한 방향이 우선합니다.

• 일회용으로 아무도 문을 사용하지 않으면 초기 상태로 돌아갑니다.

따라서 각 요소에 [t, d]가 포함된 정렬된 목록을 찾아야 합니다. 이는 시간 t에서 사람이 내부 또는 외부로 갔음을 나타냅니다.

따라서 입력이 [[2,0],[3,1],[6,0],[6,1],[3,0]]과 같으면 출력은 [[2,0] ,[3,0],[4,1],[6,1],[7,0]]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 배열 v

  정렬

• 하나의 목록 생성 ret

• curr :=1, i :=0, j :=0

• n :=v의 크기

• 동안 나는

  • ret가 비어 있지 않고 ret의 마지막 요소의 v[i, 0] - t> 1이면:

    • 커 :=1

  • j :=i + 1

  • 크기가 2인 배열 arr 정의

  • (arr[v[i, 1]] 1씩 증가)

  • 동안 (j

    • (arr[v[j, 1]] 1씩 증가)

  • t :=(ret가 비어 있으면 0, 그렇지 않으면 ret의 마지막 요소의 t) 및 v[i, 0]

    의 최대값

  • arr[1]이 0이 아니고 arr[0]이 0이 아니면 -

    • arr[curr]이 0이 아닌 동안 각 단계에서 arr[curr]을 1씩 감소시키고 -

      • ret의 끝에 {t, curr} 삽입

      • (t를 1씩 증가)

    • curr :=curr XOR 1

    • arr[curr]이 0이 아닌 동안 각 단계에서 arr[curr]을 1씩 감소시키고 -

      • ret의 끝에 {t, curr} 삽입

      • (t를 1씩 증가)

  • 그렇지 않으면

    • curr :=v[i, 1]

    • arr[curr]이 0이 아닌 동안 각 단계에서 arr[curr]을 1씩 감소시키고 -

      • ret의 끝에 {t, curr} 삽입

      • (t를 1씩 증가)

  • curr :=ret의 마지막 요소 방향

  • 나는 :=j

• 리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << "[";
      for (int j = 0; j < v[i].size(); j++) {
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]" << endl;
}
class Solution {
   public:
   vector<vector<int>> solve(vector<vector<int>>& v) {
      sort(v.begin(), v.end());
      vector < vector <int > > ret;
      int curr = 1;
      int i = 0;
      int j = 0;
      int n = v.size();
      while(i < n){
         if(!ret.empty() && v[i][0] - ret.back()[0] > 1){
            curr = 1;
         }
         j = i + 1;
         vector <int> arr(2);
         arr[v[i][1]]++;
         while(j < n && v[j][0] == v[i][0]){
            arr[v[j][1]]++;
            j++;
         }
         int t = max((ret.empty()? 0 : ret.back()[0] + 1), v[i][0]);
         if(arr[1] && arr[0]){
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
            curr = curr ^ 1;
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
         }else{
            curr = v[i][1];
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
         }
         curr = ret.back()[1];
         i = j;
      }
      return ret;
   }
};
int main(){
   vector<vector<int>> v = {{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}};
   Solution ob;
   print_vector(ob.solve(v));
}

입력

{{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}}

출력

[[2, 0, ],[3, 0, ],[4, 1, ],[6, 1, ],[7, 0, ],]