数据结构与算法实验2020夏第二批（中国石油大学） PA11题解报告——任务调度(Schedule)

目录

题目描述题目分析编码实现

一、题目描述

1. 描述

某高性能计算集群（HPC cluster）采用的任务调度器与众不同。为简化起见，假定该集群不支持多任务同时执行，故同一时刻只有单个任务处于执行状态。初始状态下，每个任务都由称作优先级数的一个整数指定优先级，该数值越小优先级越高；若优先级数相等，则任务名ASCII字典顺序低者优先。此后，CPU等资源总是被优先级数最小的任务占用；每一任务计算完毕，再选取优先级数最小下一任务。不过，这里的任务在计算结束后通常并不立即退出，而是将优先级数加倍（加倍计算所需的时间可以忽略）并继续参与调度；只有在优先级数不小于2^32时，才真正退出 你的任务是，根据初始优先级设置，按照上述调度原则，预测一批计算任务的执行序列。

2. 输入

第一行为以空格分隔的两个整数n和m，n为初始时的任务总数，m为所预测的任务执行序列长度，每行末尾有一个换行符 以下n行分别包含一个整数和一个由不超过8个小写字母和数字组成的字符串。前者为任务的初始优先级数，后者为任务名。数字和字符串之间以空格分隔

3. 输出

最多m行，各含一个字符串。按执行次序分别给出执行序列中前m个任务的名称，若执行序列少于m，那么输出调度器的任务处理完毕前的所有任务即可。

4. 例

//输入 3 3 1 hello 2 world 10 test //输出 hello hello world

5. 限制

0 ≤ n ≤ 4,000,000 0 ≤ m ≤ 2,000,000 0 < 每个任务的初始优先级 < 2^32 不会有重名的任务 时间：2 sec 内存：512 MB

6. 提示

优先级队列

二、题目分析

代码实现

首先实现一个小根堆，每次取出堆顶输出，然后将其优先级数乘2，如果优先级数小于2^32重新入队，直至执行m次取出操作或队为空。

复杂度分析：

时间复杂度：$O((m+n)logn)$空间复杂度：$O(n)$

三、编码实现

说明： 下述代码全部为【数据结构与算法实验 OJ 平台】提交过的代码。

#include <cmath> #include <cstring> #include <iostream> using namespace std; const int MAXSIZE = 1e7 + 5; struct Node1 { long long int data1; char data2[10]; friend bool operator<(Node1 x, Node1 y) { if (x.data1 != y.data1) return x.data1 < y.data1; return strcmp(x.data2, y.data2) < 0; } } h[MAXSIZE]; int n = 0; void up(int); void down(int); void Extract(); void Ins(Node1); int main() { int a, b; Node1 x; scanf("%d %d", &a, &b); long long int p = 1; for (int i = 0; i < 32; i++) p *= 2; for (int i = 0; i < a; i++) { scanf("%lld %s", &x.data1, x.data2); Ins(x); } while (b-- && n >= 1) { printf("%s\n", h[1].data2); x = h[1]; x.data1 *= 2; Extract(); if (x.data1 < p) Ins(x); } return 0; } void Ins(Node1 data1) { n += 1; h[n] = data1; up(n); } void Extract() { h[1] = h[n]; n -= 1; down(1); } void down(int p) { int temp = p * 2; while (temp <= n) { if (temp < n && h[temp + 1] < h[temp]) temp++; if (h[temp] < h[p]) { swap(h[p], h[temp]); p = temp; temp *= 2; } else break; } } void up(int p) { while (p > 1) { if (h[p] < h[p / 2]) { swap(h[p], h[p / 2]); p /= 2; } else break; } }