C++の回転ドア

リクエストのリストがあり、requests [i]に[t、d]が含まれているとします。これは、時間tに人がドアに到着し、中に入る（内側は1を使用して示す）か、外側に出る（外側はを示す）ことを示します。 0を使用します。

したがって、ドアが1つしかなく、ドアの使用に1時間単位かかる場合、従わなければならないルールはほとんどありません-

• ドアは「in」の位置で始まり、最後の参加者が使用した位置に設定されます。

• 所定の時間tにドアに参加者が1人しかいない場合、参加者はドアを使用できます。

• 2人以上の参加者が参加したい場合は、最初の参加者が最初に参加し、次に以前に使用された方向が優先されます。

• 1回限りのユニットでドアを使用する人がいない場合は、初期状態に戻ります。

したがって、各要素に[t、d]が含まれているソート済みリストを見つける必要があります。これは、時刻tに、人が内部または外部に移動したことを示します。

したがって、入力が[[2,0]、[3,1]、[6,0]、[6,1]、[3,0]]の場合、出力は[[2,0]になります。 、[3,0]、[4,1]、[6,1]、[7,0]]

これを解決するには、次の手順に従います-

• 配列を並べ替えるv

• 1つのリストを作成するret

• curr：=1、i：=0、j：=0

• n：=vのサイズ

• i

  • retが空でなく、v [i、0]-retの最後の要素のt> 1の場合、次のようになります。

    • curr：=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]がゼロ以外で、arr [0]がゼロ以外の場合、-

    • arr [curr]がゼロ以外の場合、各ステップでarr [curr]を1つずつ減らし、-

      を実行します。

      • retの最後に{t、curr}を挿入します

      • （tを1増やします）

    • curr：=curr XOR 1

    • arr [curr]がゼロ以外の場合、各ステップでarr [curr]を1つずつ減らし、-

      を実行します。

      • retの最後に{t、curr}を挿入します

      • （tを1増やします）

  • それ以外の場合

    • curr：=v [i、1]

    • arr [curr]がゼロ以外の場合、各ステップでarr [curr]を1つずつ減らし、-

      を実行します。

      • retの最後に{t、curr}を挿入します

      • （tを1増やします）

  • curr：=retの最後の要素の方向

  • i：=j

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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, ],]