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