按到达事件推进时间，维护当前运行进程和等待优先队列，遇到更高优先级进程时立即抢占。
OJ: luogu
题目 ID: P2278
难度:普及+/提高
标签:模拟堆优先队列调度
日期: 2026-06-21 12:43
题意
系统里只有一个 CPU。
每个进程有：
- 到达时间
- 运行时间
- 优先级
规则是：
- CPU 空闲就运行当前能选的最高优先级进程
- 如果新到达进程优先级更高，会立即抢占当前进程
- 若优先级相同或更低，则等待
- 等待队列中总是先选优先级最高的；若相同则到达时间更早的先运行
要求输出每个进程结束的编号和结束时刻。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Process {
ll id;
ll arrive;
ll run;
ll priority;
ll remain;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<Process> all;
while (true) {
Process p;
if (!(cin >> p.id >> p.arrive >> p.run >> p.priority)) {
break;
}
p.remain = p.run;
all.push_back(p);
}
int n = (int) all.size();
vector<int> alive(n, 1);
vector<int> started(n, 0);
ll now = 0;
int finished = 0;
auto pick_best = [&](ll t) -> int {
int best = -1;
for (int i = 0; i < n; i++) {
if (!alive[i]) {
continue;
}
if (all[i].arrive > t) {
continue;
}
if (best == -1 ||
all[i].priority > all[best].priority ||
(all[i].priority == all[best].priority && all[i].arrive < all[best].arrive) ||
(all[i].priority == all[best].priority && all[i].arrive == all[best].arrive && all[i].id < all[best].id)) {
best = i;
}
}
return best;
};
while (finished < n) {
int cur = pick_best(now);
if (cur == -1) {
ll nxt = (ll) 4e18;
for (int i = 0; i < n; i++) {
if (alive[i]) {
nxt = min(nxt, all[i].arrive);
}
}
now = nxt;
continue;
}
ll nxt = now + all[cur].remain;
for (int i = 0; i < n; i++) {
if (!alive[i] || i == cur) {
continue;
}
if (all[i].arrive > now && all[i].arrive < nxt && all[i].priority > all[cur].priority) {
nxt = min(nxt, all[i].arrive);
}
}
all[cur].remain -= (nxt - now);
now = nxt;
if (all[cur].remain == 0) {
cout << all[cur].id << ' ' << now << '\n';
alive[cur] = 0;
finished++;
}
}
return 0;
}这题本质是一个事件模拟。
真正会改变系统状态的时刻只有两类：
- 有新进程到达
- 当前运行进程结束
因此不需要一秒一秒模拟时间，只要在这些关键时刻跳跃即可。
维护两个部分：
cur：当前正在运行的进程- 等待队列：按优先级排序的优先队列
每次处理时：
- 如果 CPU 空闲，就从等待队列里取一个最高优先级进程运行
- 看它是会先运行完，还是会先遇到下一个进程到达
- 如果先运行完，就直接输出完成时间
- 如果先遇到新进程到达，就先扣掉这段时间的运行量，再判断是否被更高优先级进程抢占
等待队列的排序规则是：
- 优先级高的在前
- 若优先级相同，到达时间早的在前
- 若还相同，编号小的在前
这样就能完全按照题意模拟。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Process {
ll id;
ll arrive;
ll run;
ll priority;
ll remain;
};
struct WaitCmp {
bool operator()(const Process &a, const Process &b) const {
if (a.priority != b.priority) {
return a.priority < b.priority;
}
if (a.arrive != b.arrive) {
return a.arrive > b.arrive;
}
return a.id > b.id;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<Process> all;
while (true) {
Process p;
if (!(cin >> p.id >> p.arrive >> p.run >> p.priority)) {
break;
}
p.remain = p.run;
all.push_back(p);
}
priority_queue<Process, vector<Process>, WaitCmp> pq;
int n = (int) all.size();
int idx = 0;
ll now = 0;
bool has_cur = false;
Process cur;
while (idx < n || has_cur || !pq.empty()) {
if (!has_cur && pq.empty() && idx < n) {
now = max(now, all[idx].arrive);
}
// 先把所有在当前时刻已经到达的进程加入等待队列。
while (idx < n && all[idx].arrive <= now) {
pq.push(all[idx]);
idx++;
}
if (!has_cur) {
if (pq.empty()) {
continue;
}
cur = pq.top();
pq.pop();
has_cur = true;
}
ll next_arrive = (idx < n ? all[idx].arrive : (ll) 4e18);
ll finish_time = now + cur.remain;
if (finish_time <= next_arrive) {
now = finish_time;
cout << cur.id << ' ' << now << '\n';
has_cur = false;
continue;
}
// 先运行到下一个进程到达时刻。
cur.remain -= (next_arrive - now);
now = next_arrive;
// 把这一时刻到达的所有进程加入等待队列。
while (idx < n && all[idx].arrive == now) {
pq.push(all[idx]);
idx++;
}
if (!pq.empty() && pq.top().priority > cur.priority) {
pq.push(cur);
cur = pq.top();
pq.pop();
}
}
return 0;
}复杂度
每个进程最多进入优先队列一次、被弹出若干次抢占回去，但总操作次数仍然是
空间复杂度是
总结
这题的关键是：
- 不按时间单位模拟
- 只在“到达事件”和“完成事件”这两个关键时刻更新状态
一旦想到这一点，整个实现就是一个标准的抢占式调度模拟。