<>题目描述

读入任务调度序列,输出n个任务适合的一种调度方式。

<>输入

输入包含多组测试数据。

每组第一行输入一个整数n(n<100000),表示有n个任务。

接下来n行,每行第一个表示前序任务,括号中的任务为若干个后序任务,表示只有在前序任务完成的情况下,后序任务才能开始。若后序为NULL则表示无后继任务。

<>输出

输出调度方式,输出如果有多种适合的调度方式,请输出字典序最小的一种。

<>样例输入
4 Task0(Task1,Task2) Task1(Task3) Task2(NULL) Task3(NULL)
<>样例输出
Task0 Task1 Task2 Task3
思路:用优先队列,可以用一个结构体来存放任务,用x来定义优先级大小,越小的越优先(先输入的优先)。
每当输入一行字符串后,从该字符串里获取任务的单词,获取之后将该单词散列至哈希表里,下次再出现它是对它不处理,具体代码如下:
#include <map> #include <cstdio> #include <iostream> #include <queue> #include
<string> #include <cctype> using namespace std; struct task{ //任务结构体 string s;
//任务名 int x; //任务的优先级 friend bool operator < (task a,task b){ if(a.s!=b.s)
return a.x>b.x; //如果任务名不同,则x小的优先 else return a.s>b.s; //否则按字典序小的优先 } }t; int
main() { map<string,bool> hashTable; //哈希表,用于确定该任务是否出现过 priority_queue<task> q;
//优先队列,用于存放任务 string s,word; //s是每行字符串,word用于获取任务 int n,i,j,k; while(scanf(
"%d\n",&n)!=EOF){ k=0; //先置优先级为0(小的优先) for(i=0;i<n;i++){ getline(cin,s); for(j=0
;j<s.length();j++){ //获取任务的单词 if(isalnum(s[j])) //任务由字母和数字组成,如果符合条件,则放入word中
word.push_back(s[j]); else //不符合条件,比如遇到"("等情况则清空单词 word.clear(); if(!word.empty(
)&&!isalnum(s[j+1])){ 表示已经获取到了完整的单词 if(word=="NULL") //如果是NULL则跳过 continue; if(
hashTable[word]==false){ //该任务没出现过,则进行操作 hashTable[word]=true;
//置true,下次遇到它时不做操作 t.s=word; t.x=k++; q.push(t); //将任务结构体入队 } else continue; } }
} //输出过程 cout <<q.top().s; q.pop(); while(!q.empty()){ cout <<" "<<q.top().s; q.
pop(); } cout <<endl; } return 0; }

技术
©2019-2020 Toolsou All rights reserved,
Vue.js入门(五)---在vue中使用echarts词云Pandas统计分析基础_数据处理(DataFrame常用操作)element UI dialog点击dialog区域外会关闭dialog应届毕业生看过来!Java面试经典77问,看完离工作就不远了关于蓝桥杯大赛,你应该了解的那些事!mysql 分区-key分区(五)海康威视-嵌入式软件笔试题PHP Redis 监听过期的 key 事件C语言循环语句笔记详解以及练习-折半查找算法、猜数字游戏JVM概述