1 条题解
-
0
按题意模拟过程即可。
一些实现方法:
给每个人开一个结构体,按照按电梯的时间和员工编号排序。
开一个队列记录收到的信号请求。
由于电梯下行过程中还会接到其他人,所以还需要另开队列或结构体数组把每个人按照楼层排序。
维护一个当前时间,接到新的员工时更新为他的按电梯时间,送完一班乘客后加上 。
注意一个数据会在两个队列中均出现,所以记得判断当前计算的员工是否已经到达一楼。
用 维护。代码
#include <bits/stdc++.h> #define ll long long #define For(i,a,b) for(int i=(a);i<=(b);++i) #define Rof(i,a,b) for(int i=(a);i>=(b);--i) using namespace std; const int Maxn = 2e5; int n, m, t[Maxn + 5], a[Maxn + 5], pos; ll tim, val = 1, ans[Maxn + 5]; set<int> s1; set<pair<int, int>> s2; inline void Add() { while (pos <= n && t[pos] <= tim) s1.insert(pos), s2.insert(make_pair(a[pos], pos)), pos++; } int main() { // freopen("rest.in", "r", stdin); // freopen("rest.out", "w", stdout); cin >> n >> m; For(i, 1, n) cin >> t[i] >> a[i]; while (1) { if (s1.empty()) { if (pos > n) break; tim = t[pos]; } Add(); int x = *s1.begin(); tim += a[x] - 1, val = a[x]; while (val != 1) { Add(); while (1) { auto it = s2.lower_bound(make_pair(val, 0)); if (it != s2.end() && it->first == val) { int k = it->second; ans[k] = tim + val - 1; s1.erase(k), s2.erase(it); } else break; } int nxt = val - 1; if (pos <= n) nxt = min(1ll * nxt, t[pos] - tim); auto it = s2.lower_bound(make_pair(val, 0)); if (it != s2.begin()) nxt = min(1ll * nxt, val - prev(it)->first); tim += nxt, val -= nxt; } } For(i, 1, n) printf("%lld\n", ans[i]); return 0; }
- 1
信息
- ID
- 10255
- 时间
- 800ms
- 内存
- 512MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者