题解 | #[HNOI2003]操作系统#

#include<iostream>
#include<queue>
using namespace std;

struct mode {
	int name;
	int beg;
	int time;
	int value;
}jc;

bool operator<(const mode &a, const mode &b) {
    if(a.value==b.value)return a.name>b.name;
	return a.value < b.value;
}

int main() {
	int now = 0, deadline = 0;
	priority_queue<struct mode>pq;
	cin >> jc.name >> jc.beg >> jc.time >> jc.value;
	pq.push(jc);
	now = jc.beg;
	while (cin >> jc.name >> jc.beg >> jc.time >> jc.value) {
		deadline = jc.beg;
		while (now < deadline) {
			if (pq.empty()) {
				now = deadline;
				break;
			}
			else if (now + pq.top().time <= deadline) {
				now += pq.top().time;
				cout << pq.top().name << " " << now << endl;
				pq.pop();
			}
			else {
				struct mode shadow = pq.top();
				shadow.time -= (deadline - now);
				now = deadline;
				pq.pop();
				pq.push(shadow);
			}
		}
        pq.push(jc);
	}
    while(!pq.empty()){
        cout << pq.top().name << " " << now + pq.top().time<<endl;
        now+=pq.top().time;
        pq.pop();
    }
}

这道题分类比较麻烦而且容易错，不好打断点但是可以在不同分支中打唯一标记输出来微调（忽视这句话）。这题我的具体做法是先塞一个进程进队列，然后设置一个deadline为下一个进来的进程到达的时间（为什么选择以这个作为时间点，原因是我们并不知道队列中的top优先级是否高于进来的新进程，那么对于每一个时间段来说要执行哪个进程就成了问题，诚然可以全读入再对整体处理，但那样不仅处理极其繁琐并且没有利用到数据按照进程到来顺序给定这个条件会扩大复杂度，虽然这题数据很水基本不会爆爆爆），now作为当前执行到的时间点（因为要求输出的是进程名和结束时间，如果直接用时间线上的点来表示利于我们中断退出而且不容易出错，涉及数据少容易调试），now随着时间的推进要与时俱进地更新，时间是否推进是根据每一段时间的归属决定的，时间判断出归属某个进程以后，最后要记得更新now。，这样对于执行情况来说会有两种，一种是当前队列中的优先级top进程能在下一个进程到达之前直接跑完，那么我们就直接让它跑完，输出它然后让它退出；一种则是进程的所需执行时间比较长，在下一个进程到达前跑不完，所以我们考虑到一个问题如何记录下没跑完的情况呢？没错就是利用执行时间time属性，在我的设计中它也有剩余所需执行时间的含义，我们让time减去对应这段的时间来更新time值就行了（这里需要提一下可以看到我用了一个结构体shadow来复制了队列的最高优先级进程top，因为这道题涉及到结构体进入优先队列的比较规则问题，我重载了比较规则operator，考虑到优先级越高的自然越前，但同时存在优先级相同的情况，所以需要单独写一条如果优先级相同按照进程名字保持原顺序不变（这是因为这道题数据很水，测试数据的进程名都是升序排列的，其实但凡给你的进程号有一个前面大于后面的hack数据直接爆炸。更精密一点的写法是给每个进程按照进来的顺序额外上一个升序编号，按照这个编号来排列而不是name排列就不会有这样的隐患，我因为懒这里没有弄，估计所有测试数据里进程号升序给你单纯是出题人的仁慈）。结构体里面的各元素可以看到传参是const修饰引用类型的，所以不能直接改变他们里面的数值，必须复制一份，在队列外才能更新time属性值，再从队列中删除top进程,最后用我们的复制品shadow加入队列完成替换），当time成0时代表一个进程剩余的所需执行时间没了也就是它跑完了的意思，那自然可以输出他然后让他退出。想到这里还没完，因为now还没到deadline，即下个进程还没到来，如果队列中还存在进程，那么也是需要继续进行的（具体怎么进行的和上面一样，所以能看到我程序里用了一个while（now<deadline）,这是循环判断的意思），如果队列中进程全跑完了一个没有了那么直接把now拉到下个进程jc到来的时间点deadline退出循环。然后让jc进队（因为jc在新循环马上要接收新的值了，无论前面的进程跑完了没，jc已经到了，自然要进队，至于优先级，优先队列会按照我们重载后的比较规则自己排列维护的，我们不用管这些细节）。这样还没完，最后可能存在所有程序都到了但是进程队列中因为种种原因滞留进程导致进程数量事实上不一定为1而是>=1,所以需要写一个循环while(!pq.empty())来切掉所有剩下的进程，这里的处理就会相对比较简单，因为没有新的进程会加进来的，所以只需要按照优先队列的顺序，挨个跑完top进程每一步都更新now输出就行了。