Processing math: 100%

C++中的旋转门


假设我们有一系列请求,其中requests[i]包含[t, d],表示在t时刻,一个人到达门口,并想进入(用1表示)或出去(用0表示)。

所以如果只有一个门,并且使用门需要一个时间单位,我们必须遵循一些规则:

  • 门最初处于“进入”状态,然后设置为最后一位参与者使用的状态。

  • 如果在给定时间t只有一个参与者在门口,他们可以使用门。

  • 如果两个或多个参与者想进入,则最早到达的参与者优先,然后先前使用的方向具有优先权。

  • 如果没有人使用门一个时间单位,它会恢复到初始状态。

因此,我们必须找到一个排序列表,其中每个元素都包含[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的大小

  • 当i < n时,执行:

    • 如果ret不为空且v[i, 0] - ret的最后一个元素的t > 1,则

      • curr := 1

    • j := i + 1

    • 定义一个大小为2的数组arr

    • (将arr[v[i, 1]]加1)

    • 当(j < n且v[j, 0]与v[i, 0]相同)时,执行:

      • (将arr[v[j, 1]]加1)

    • t := max((如果ret为空,则为0,否则为ret的最后一个元素的t)和v[i, 0])

    • 如果arr[1]不为零且arr[0]不为零,则:

      • 当arr[curr]不为零时,每步将arr[curr]减一,执行:

        • 将{t, curr}插入到ret的末尾

        • (将t加1)

      • curr := curr XOR 1

      • 当arr[curr]不为零时,每步将arr[curr]减一,执行:

        • 将{t, curr}插入到ret的末尾

        • (将t加1)

    • 否则

      • curr := v[i, 1]

      • 当arr[curr]不为零时,每步将arr[curr]减一,执行:

        • 将{t, curr}插入到ret的末尾

        • (将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}}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

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

更新于:2020年9月2日

241 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告