【HNOI2003】操作系统Java
题目描述
链接：https://ac.nowcoder.com/acm/problem/20030
来源：牛客网
写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。
如果一个进程到达的时候CPU是空闲的，则它会一直占用CPU直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用CPU，而老的只有等待。
如果一个进程到达时，CPU正在处理一个比它优先级高或优先级相同的进程，则这个（新到达的）进程必须等待。一旦CPU空闲，如果此时有进程在等待，则选择优先级最高的先运行。如果有多个优先级最高的进程，则选择到达时间最早的。
输入
1 1 5 3
2 10 5 1
3 12 7 2
4 20 2 3
5 21 9 4
6 22 2 4
7 23 5 2
8 24 2 4
输出
1 6
3 19
5 30
6 32
8 34
4 35
7 40
2 42
思路
用优先队列大家都能想到，按照题目给的条件进行模拟，先按照优先级从大到小进行排序，如果优先级相同，则按照到达时间短的排前面。本题是一个抢占式的进程调度，如果当前时间有进程占用CPU，而到达的进程优先级比它高，那么就会抢占。因此我们可以按照这个思路进行模拟。
如果当前进程执行时间 < 下一个进程到达时间 - 当前时间。那么就可能会被抢占，先放到队列里。
否则，该进程会执行完。
这里进程是按照时间顺序进入的优先队列。
注意：这里要用PrintWriter，不能使用System.out.println()，由于可以手动控制缓冲区的刷新，PrintWriter 在处理大量数据时可能比 System.out.println() 更高效。
代码
import java.io.PrintWriter;
import java.util.*;public class Main{public static void main(String[] args) {Scanner in = new Scanner(System.in);PrintWriter out = new PrintWriter(System.out);PriorityQueue<Process> pq = new PriorityQueue<>();List<int[]> ans = new ArrayList<>();List<Process> list = new ArrayList<>();while(in.hasNext()) {int id = in.nextInt();int arrTime = in.nextInt();int execTime = in.nextInt();int prior = in.nextInt();list.add(new Process(id, arrTime, execTime, prior));}int curTime = 0;int ind = 0;while (ind < list.size()) {if (pq.isEmpty()) {curTime = list.get(ind).arrivalTime; // 当前时间是下一个进程到达的时间} else {Process top = pq.poll();int diff = Math.min(top.executionTime, list.get(ind).arrivalTime - curTime);curTime += diff;top.executionTime -= diff;if (top.executionTime == 0) {ans.add(new int[] {top.id, curTime});} else {pq.offer(top);}}while (ind < list.size() && list.get(ind).arrivalTime <= curTime) {pq.offer(list.get(ind++));}}while (!pq.isEmpty()) {Process a = pq.poll();curTime += a.executionTime;ans.add(new int[]{a.id, curTime});}for (int[] a : ans) {out.println(a[0] + " " + a[1]);}out.close();}
}
class Process implements Comparable {int id;int arrivalTime;int executionTime;int priority;public Process(int id, int arrivalTime, int executionTime, int priority) {this.id = id;this.arrivalTime = arrivalTime;this.executionTime = executionTime;this.priority = priority;}@Overridepublic int compareTo(Object o) {if (this.priority != ((Process) o).priority) {return Integer.compare(((Process) o).priority, this.priority); // 从大到小排序} else {return Integer.compare(this.arrivalTime, ((Process) o).arrivalTime); // 从小到大排序}}
}