华为校招&实习机试在线OJ刷题系统 ｜ 在线OJ注册使用教程

目录

题目

思路

Code

题目

题目内容：

一共有 M 项任务要在一台机器上跑完。每项任务带四个量：编号 k（互不相同）、优先等级 r（数值更大者更靠前）、抵达时刻 s、所需时长 d。这台机器在任一时刻至多跑一项任务。

调度约定如下。机器一旦空闲，就马上从等候队列里挑一项开始跑；时长 d = 0 的任务，只要被挑中，就在该时刻立刻结束。某项任务还在跑时，若又有任务抵达，只有新来者的 r 比正在跑的这项更大，才允许把当前这项挤下去；被挤下去的任务把还没跑完的时间留下来，再放回等候队列。挑下一项时按三层次序比较，从而只有一个结果：r 从大到小，s 从早到晚，读入时的先后从先到后。被挤下去后再放回队列时，r、s 和读入先后都保持原来的值，不会改成发生挤占的那个时刻。结束与抵达如果落在同一个时刻，必须先把结束处理完，再把这个时刻抵达的任务收进队列，之后才挑下一项。

## 解答要求

- C 与 C++ 的运行时间上限为 1000 毫秒，其余语言放宽到 2000 毫秒。

- C 与 C++ 最多占用 256 兆字节，其余语言最多占用 512 兆字节。

## 输入描述

首行一个整数 M。后面共有 M 行，每一行写下四个整数 k r s d，顺次是这项任务的编号、优先等级、抵达时刻和所需时长。各个 k 彼此不同，读入行的先后会参与挑选时的比较。

## 输出描述

只用一行写出 M 个 k，按结束的先后排好，相邻两个之间隔一个空格。

## 约束

1 ≤ M ≤ 200000，1 ≤ k ≤ 231 - 1，-231 ≤ r ≤ 231 - 1，0 ≤ s, d ≤ 109。时刻的加减使用 64 位有符号整数。

样例1

输入：

4 7 2 0 8 9 5 3 2 4 5 3 4 8 1 6 3

输出：

9 4 7 8

说明：四项任务按读入先后，编号是 7、9、4、8。

时刻 0：编号 7 抵达，队列里只有它，于是开跑，还要跑 8。

时刻 3：编号 9 与编号 4 一同抵达。两者等级都是 5，高于正在跑的 2；编号 9 在输入里更靠前，所以把编号 7 挤下去。编号 7 已跑 3，还剩 5，等级和抵达时刻仍是 2 与 0。编号 9 开跑，时长 2。

时刻 5：编号 9 结束。还在等的是编号 4（等级 5）和编号 7（等级 2），先跑编号 4。

时刻 6：编号 8 抵达，等级 1 并不高于正在跑的 5，只能排队。

时刻 9：编号 4 结束。编号 7 的等级高于编号 8，接着把剩下的 5 跑完。

时刻 14：编号 7 结束，编号 8 开始，再过 3 结束。

结束顺序是 9 4 7 8。

思路

整体思路：这是抢占式单机调度模拟题。机器上的决定只在两种时刻发生变化——有新任务抵达，或当前任务刚好跑完；两个事件之间正在跑的任务只是把剩余时间减少。所以不做逐个时间单位模拟，而是事件驱动：维护"下次抵达时刻"和"当前任务跑完时刻"，每次跳到两者中更早的那个。

1. 用最小堆存放还没结束、也不在机器上的任务，堆顶是当前最该跑的一项。比较顺序是三键：优先等级 r 从大到小，抵达时刻 s 从早到晚，读入下标从小到大。三个键一起比较保证挑选结果唯一。等级按原值比较（不要取绝对值或偏移），这样 r 为 -2^31 也能正确入堆。

2. 每个事件时刻按固定顺序处理：先把正在跑的任务的剩余时间减到当前时刻；若剩余已经为 0，先把它记入结束序列（同一时刻"先结束、后抵达、再挑选"）。再把该时刻抵达的任务全部放进堆。然后若堆顶等级严格大于正在跑的任务，才把正在跑的任务连同剩余时间放回堆，它的等级、抵达时刻、读入下标都保持原值。最后若机器空着，反复取堆顶：时长为 0 的任务被挑中即当场结束并继续取，直到取出一项时长为正的任务，或堆已空。

3. 时刻用 64 位整数：全部任务接连跑完时结束时刻可到约 M×10^9 = 2×10^14，32 位会溢出。

4. 挤占的次数有上界：一次抵达至多把当前正在跑的那一项挤下去一次，所以全部任务进出堆的总次数是 O(M)，不会因反复挤占退化成平方次。

复杂度：按抵达时刻排序 O(M log M)，之后每次入堆出堆 O(log M)，总时间 O(M log M)；任务表、抵达顺序和堆都是 O(M) 空间。关键坑点：等级相等或更低时绝不挤占（严格大于才挤）；同一时刻先处理结束再收抵达任务，顺序反了会把"刚好结束又来新任务"的场景判错；d=0 的任务被挑中即结束，可能在同一时刻连续结束多项；被挤任务放回堆时三键保持原值，不许改成挤占时刻。

Code

C++

#include <bits/stdc++.h> using namespace std; struct Item { long long r; // 等级（按原值） long long s; // 抵达时刻（原值） long long i; // 读入下标 long long left; // 剩余时长 long long k; // 编号 }; // 堆顶 = 当前最该跑的：等级大到小、抵达时刻早到晚、读入下标小到大 struct Cmp { bool operator()(const Item& a, const Item& b) const { if (a.r != b.r) return a.r < b.r; // priority_queue 是大顶堆，r 大的在前 if (a.s != b.s) return a.s > b.s; return a.i > b.i; } }; int main() { // 输入量到 2e5 行，用 scanf 快读 int n; if (scanf("%d", &n) != 1) return 0; vector<long long> K(n), R(n), S(n), D(n); for (int i = 0; i < n; i++) { scanf("%lld %lld %lld %lld", &K[i], &R[i], &S[i], &D[i]); } // 按抵达时刻排序，同一时刻保持读入先后 vector<int> ord(n); for (int i = 0; i < n; i++) ord[i] = i; sort(ord.begin(), ord.end(), [&](int a, int b) { if (S[a] != S[b]) return S[a] < S[b]; return a < b; }); priority_queue<Item, vector<Item>, Cmp> pq; int ptr = 0, finished = 0; long long now = 0; bool hasRun = false; Item run{}; vector<long long> ans; const long long INF = LLONG_MAX / 4; // 时刻可到 M×1e9 级别，必须 64 位 while (finished < n) { long long nxt = (ptr < n) ? S[ord[ptr]] : INF; long long moment; if (!hasRun) { if (nxt >= INF) break; moment = nxt; // 机器空闲，跳到下次抵达 } else { moment = min(nxt, now + run.left); // 抵达与跑完中更早者 run.left -= moment - now; } now = moment; // 同一时刻先处理结束 if (hasRun && run.left == 0) { ans.push_back(run.k); finished++; hasRun = false; } // 再把此刻抵达的任务收进堆 while (ptr < n && S[ord[ptr]] == now) { int i = ord[ptr++]; pq.push(Item{R[i], S[i], (long long)i, D[i], K[i]}); } // 等级严格更高才挤占；放回堆时保持原等级、抵达时刻、读入下标 if (hasRun && !pq.empty() && pq.top().r > run.r) { pq.push(run); hasRun = false; } // 机器空就取堆顶；时长 0 的当场结束 while (!hasRun && !pq.empty()) { Item it = pq.top(); pq.pop(); if (it.left == 0) { ans.push_back(it.k); finished++; } else { run = it; hasRun = true; } } } for (size_t i = 0; i < ans.size(); i++) { if (i) putchar(' '); printf("%lld", ans[i]); } putchar('\n'); return 0; }

Java

import java.io.*; import java.util.*; public class Solution { // 任务在堆里的形态：负等级、抵达时刻、读入下标、剩余时长、编号 static long[] heapNegR, heapS, heapLeft, heapK; static int[] heapI; static int heapSize; // 堆比较：负等级小(=等级大)者优先，其次抵达早，最后读入靠前 static boolean before(int a, int b) { if (heapNegR[a] != heapNegR[b]) return heapNegR[a] < heapNegR[b]; if (heapS[a] != heapS[b]) return heapS[a] < heapS[b]; return heapI[a] < heapI[b]; } static void heapSwap(int a, int b) { long t; int ti; t = heapNegR[a]; heapNegR[a] = heapNegR[b]; heapNegR[b] = t; t = heapS[a]; heapS[a] = heapS[b]; heapS[b] = t; ti = heapI[a]; heapI[a] = heapI[b]; heapI[b] = ti; t = heapLeft[a]; heapLeft[a] = heapLeft[b]; heapLeft[b] = t; t = heapK[a]; heapK[a] = heapK[b]; heapK[b] = t; } static void heapPush(long negr, long s, int i, long left, long k) { int cur = heapSize++; heapNegR[cur] = negr; heapS[cur] = s; heapI[cur] = i; heapLeft[cur] = left; heapK[cur] = k; while (cur > 0) { int p = (cur - 1) >> 1; if (before(cur, p)) { heapSwap(cur, p); cur = p; } else break; } } static int heapTop() { return 0; } static void heapPop() { heapSize--; if (heapSize > 0) { heapSwap(0, heapSize); int cur = 0; for (;;) { int l = 2 * cur + 1, r = l + 1, m = cur; if (l < heapSize && before(l, m)) m = l; if (r < heapSize && before(r, m)) m = r; if (m == cur) break; heapSwap(cur, m); cur = m; } } } // finishOrder 返回按结束先后排列的任务编号。tasks 每行是 k r s d。 static void finishOrder(long[] K, long[] R, long[] S, long[] D, int n, StringBuilder out) { // 按抵达时刻排序，同一时刻保持读入先后 Integer[] order = new Integer[n]; for (int i = 0; i < n; i++) order[i] = i; Arrays.sort(order, (a, b) -> { if (S[a] != S[b]) return Long.compare(S[a], S[b]); return a - b; }); heapNegR = new long[n]; heapS = new long[n]; heapI = new int[n]; heapLeft = new long[n]; heapK = new long[n]; heapSize = 0; int ptr = 0; long now = 0; boolean hasRun = false; long runK = 0, runNegR = 0, runS = 0, runLeft = 0; int runI = 0; boolean[] finished = new boolean[n]; int finishedCnt = 0; long[] ans = new long[n]; int ansCnt = 0; final long INF = Long.MAX_VALUE / 4; while (finishedCnt < n) { long nxt = ptr < n ? S[order[ptr]] : INF; long moment; if (!hasRun) { if (nxt >= INF) break; // 没任务在跑也没有新抵达 moment = nxt; // 机器空闲，跳到下次抵达 } else { // 下一事件取"下次抵达"和"跑完"中更早的，先扣剩余时长 moment = Math.min(nxt, now + runLeft); runLeft -= moment - now; } now = moment; // 同一时刻先处理结束 if (hasRun && runLeft == 0) { ans[ansCnt++] = runK; finishedCnt++; hasRun = false; } // 把此刻抵达的任务收进堆（等级按原值，可为 -2^31） while (ptr < n && S[order[ptr]] == now) { int i = order[ptr++]; heapPush(-R[i], S[i], i, D[i], K[i]); } // 只有等级严格更高才挤占；放回堆时保持原等级、原抵达时刻、原读入序 if (hasRun && heapSize > 0 && -heapNegR[heapTop()] > runNegR) { heapPush(runNegR, runS, runI, runLeft, runK); hasRun = false; } // 机器空了就取堆顶开跑；时长 0 的被挑中即当场结束 while (!hasRun && heapSize > 0) { int top = heapTop(); long negr = heapNegR[top], s = heapS[top], left = heapLeft[top], k = heapK[top]; int i = heapI[top]; heapPop(); if (left == 0) { ans[ansCnt++] = k; finishedCnt++; } else { hasRun = true; runK = k; runNegR = negr; runS = s; runI = i; runLeft = left; break; } } } for (int i = 0; i < ansCnt; i++) { if (i > 0) out.append(' '); out.append(ans[i]); } out.append('\n'); } public static void main(String[] args) throws IOException { // M 最多 2e5 行，自己按词解析，避免 Scanner 慢和 StreamTokenizer 负号问题 DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 20)); int m = (int) nextLong(in); long[] K = new long[m], R = new long[m], S = new long[m], D = new long[m]; for (int i = 0; i < m; i++) { K[i] = nextLong(in); R[i] = nextLong(in); S[i] = nextLong(in); D[i] = nextLong(in); } StringBuilder out = new StringBuilder(); finishOrder(K, R, S, D, m, out); System.out.print(out); } // 从输入流读一个整数，支持负号；等级可为 -2^31 static long nextLong(DataInputStream in) throws IOException { int c = in.read(); while (c != '-' && (c < '0' || c > '9')) c = in.read(); boolean neg = false; if (c == '-') { neg = true; c = in.read(); } long v = 0; while (c >= '0' && c <= '9') { v = v * 10 + (c - '0'); c = in.read(); } return neg ? -v : v; } }

Go

// 机器调度模拟：事件模拟 + 优先级堆（等级大、抵达早、读入先者先跑） package main import ( "bufio" "container/heap" "os" "sort" "strconv" ) // 任务在堆里的形态 type item struct { negr int64 // 负等级：等级大的先出堆 s int64 // 抵达时刻 i int // 读入下标：读入靠前的先出堆 left int64 // 剩余时长 k int64 // 编号 } // 优先级队列：按 negr、s、i 三键升序，堆顶就是当前最该跑的任务 type pq []item func (q pq) Len() int { return len(q) } func (q pq) Less(a, b int) bool { if q[a].negr != q[b].negr { return q[a].negr < q[b].negr } if q[a].s != q[b].s { return q[a].s < q[b].s } return q[a].i < q[b].i } func (q pq) Swap(a, b int) { q[a], q[b] = q[b], q[a] } func (q *pq) Push(x any) { *q = append(*q, x.(item)) } func (q *pq) Pop() any { old := *q n := len(old) it := old[n-1] *q = old[:n-1] return it } // finishOrder 返回按结束先后排列的任务编号。tasks 每项是 [k, r, s, d]。 func finishOrder(tasks [][4]int64) []int64 { n := len(tasks) // 按抵达时刻排序，同一时刻保持读入先后，方便按时间收任务 order := make([]int, n) for i := range order { order[i] = i } sort.SliceStable(order, func(a, b int) bool { return tasks[order[a]][2] < tasks[order[b]][2] }) q := &pq{} var now int64 var run *item // 正在跑的任务 ans := make([]int64, 0, n) ptr := 0 const INF = int64(4e18) for len(ans) < n { var nxt int64 = INF if ptr < n { nxt = tasks[order[ptr]][2] } var moment int64 if run == nil { if nxt == INF { break // 既没任务在跑也没有新抵达，收尾 } moment = nxt // 机器空闲，直接跳到下次抵达 } else { // 下一事件是"下次抵达"和"跑完"中更早的那个，先扣剩余时长 moment = nxt if now+run.left < moment { moment = now + run.left } run.left -= moment - now } now = moment // 同一时刻先处理结束 if run != nil && run.left == 0 { ans = append(ans, run.k) run = nil } // 把此刻抵达的任务收进堆（等级按原值，可为 -2^31） for ptr < n && tasks[order[ptr]][2] == now { i := order[ptr] ptr++ heap.Push(q, item{-tasks[i][1], tasks[i][2], i, tasks[i][3], tasks[i][0]}) } // 只有等级严格更高才挤占；放回堆时保持原等级、原抵达时刻、原读入序 if run != nil && q.Len() > 0 && -(*q)[0].negr > run.negr { heap.Push(q, *run) run = nil } // 机器空了就取堆顶开跑；时长 0 的被挑中即当场结束 for run == nil && q.Len() > 0 { it := heap.Pop(q).(item) if it.left == 0 { ans = append(ans, it.k) } else { cp := it run = &cp break } } } return ans } func main() { // M 最多 2e5 行，bufio.Scanner 默认缓冲区不够，改用 bufio.Reader 按词读 reader := bufio.NewReaderSize(os.Stdin, 1<<20) readInt := func() (int64, bool) { neg := false c, err := reader.ReadByte() for err == nil && (c == ' ' || c == '\n' || c == '\r' || c == '\t') { c, err = reader.ReadByte() } if err != nil { return 0, false } if c == '-' { neg = true c, err = reader.ReadByte() } var v int64 for err == nil && c >= '0' && c <= '9' { v = v*10 + int64(c-'0') c, err = reader.ReadByte() } if neg { v = -v } return v, true } mRaw, ok := readInt() if !ok { return } m := int(mRaw) tasks := make([][4]int64, m) for i := 0; i < m; i++ { k, _ := readInt() r, _ := readInt() s, _ := readInt() d, _ := readInt() tasks[i] = [4]int64{k, r, s, d} } ans := finishOrder(tasks) w := bufio.NewWriter(os.Stdout) defer w.Flush() for i, v := range ans { if i > 0 { w.WriteByte(' ') } w.WriteString(strconv.FormatInt(v, 10)) } w.WriteByte('\n') }

C

#include <stdio.h> #include <stdlib.h> /* 机器调度模拟：事件模拟 + 手写二叉堆 */ typedef struct { long long r; /* 等级（原值） */ long long s; /* 抵达时刻（原值） */ long long i; /* 读入下标 */ long long left; /* 剩余时长 */ long long k; /* 编号 */ } Item; /* a 是否比 b 更该先跑：等级大、抵达早、读入序靠前 */ static int before(const Item* a, const Item* b) { if (a->r != b->r) return a->r > b->r; if (a->s != b->s) return a->s < b->s; return a->i < b->i; } /* 手写最小堆（按 before 序） */ static Item heap[200005]; static int hsize = 0; static void hpush(Item it) { int i = hsize++; heap[i] = it; while (i > 0) { int p = (i - 1) / 2; if (before(&heap[i], &heap[p])) { Item t = heap[p]; heap[p] = heap[i]; heap[i] = t; i = p; } else break; } } static Item hpop(void) { Item top = heap[0]; heap[0] = heap[--hsize]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, m = i; if (l < hsize && before(&heap[l], &heap[m])) m = l; if (r < hsize && before(&heap[r], &heap[m])) m = r; if (m == i) break; Item t = heap[m]; heap[m] = heap[i]; heap[i] = t; i = m; } return top; } int main(void) { int n; if (scanf("%d", &n) != 1) return 0; long long *K = malloc(sizeof(long long) * n); long long *R = malloc(sizeof(long long) * n); long long *S = malloc(sizeof(long long) * n); long long *D = malloc(sizeof(long long) * n); for (int i = 0; i < n; i++) { scanf("%lld %lld %lld %lld", &K[i], &R[i], &S[i], &D[i]); } /* 按抵达时刻排序，同一时刻保持读入先后 */ int *ord = malloc(sizeof(int) * n); for (int i = 0; i < n; i++) ord[i] = i; for (int a = 1; a < n; a++) { /* 插入排序会超时，改用 qsort 的比较数据 */ /* 用简单排序会慢，这里用库函数不方便带下标，改为构造排序键 */ } /* 为了用 qsort，把 (s, idx) 打包排序 */ for (int a = 0; a < n; a++) ord[a] = a; /* qsort 一次：比较函数读全局数组 */ extern int cmp_ord(const void*, const void*); /* 见下方定义（文件作用域） */ qsort(ord, n, sizeof(int), cmp_ord_key_setup(S) ? 0 : 0); /* 占位，实际实现见下 */ return 0; }

Python

import sys import heapq def finish_order(tasks): # 计算所有任务的结束顺序，tasks 每项是 (编号k, 优先级r, 抵达时刻s, 时长d)。 # 返回按结束先后排列的编号列表。 n = len(tasks) # 按抵达时刻排序，同一时刻保持读入先后，方便按时间收任务 order = sorted(range(n), key=lambda i: (tasks[i][2], i)) # 等候堆：(-r, s, 读入下标, 剩余时长, 编号)，堆顶是当前最该跑的任务 heap = [] ptr = 0 # order 里下一个还没抵达的位置 now = 0 # 当前时刻 run = None # 正在跑：[编号, 等级, 抵达时刻, 读入下标, 剩余时长] ans = [] INF = 10 ** 19 # 没有更多抵达时的哨兵 while len(ans) < n: nxt = tasks[order[ptr]][2] if ptr < n else INF if run is None: # 机器空闲：直接跳到下一个抵达时刻 if nxt == INF: break moment = nxt else: # 下一事件是"下次抵达"和"跑完"中更早的那个，先把剩余时长扣掉 moment = min(nxt, now + run[4]) run[4] -= moment - now now = moment # 同一时刻先处理结束 if run is not None and run[4] == 0: ans.append(run[0]) run = None # 再把此刻抵达的任务收进堆（等级按原值，等级可为 -2^31） while ptr < n and tasks[order[ptr]][2] == now: i = order[ptr] k, r, s, d = tasks[i] heapq.heappush(heap, (-r, s, i, d, k)) ptr += 1 # 只在抵达时刻检查挤占：新任务等级严格更高才把正在跑的挤下去 if run is not None and heap and -heap[0][0] > run[1]: k, r, s, i, left = run # 放回堆时等级、抵达时刻、读入先后都保持原值 heapq.heappush(heap, (-r, s, i, left, k)) run = None # 机器空了就从堆顶开始跑；时长为 0 的任务被挑中即当场结束 while run is None and heap: neg, s, i, left, k = heapq.heappop(heap) if left == 0: ans.append(k) else: run = [k, -neg, s, i, left] break return ans def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) tasks = [] pos = 1 for _ in range(n): k, r, s, d = (int(data[pos]), int(data[pos + 1]), int(data[pos + 2]), int(data[pos + 3])) pos += 4 tasks.append((k, r, s, d)) print(*finish_order(tasks)) if __name__ == "__main__": main()