任务调度
http://codeup.cn/problem.php?cid=100000601&pid=0
前言:
Codeup上priority_queue的一道题
题目简述:
给定n个任务,每次读入一行字符串。括号前的为前序任务,括号内的为后续任务(如果是NULL,则表示没有后续任务)。且只有当前序任务完成后,后续任务才能开始。
序幕:
1、看到题目首先思考怎么处理输入,想到string
2、因为任务之间有先后关系,所以想到priority_queue(优先队列)
3、在编码过程中,发现不知道怎么确定任务之间的顺序,即怎么入队;思考了一下,想到了另一种STL容器——能实现映射的map,但是具体实现感觉很麻烦,就卡在了这里
4、上网去查找这道题,想找点更简单清晰的思路,发现大佬们大部分确实是用的priority_queue和unordered_map,但是代码有点复杂,就没有采用(实际上就是我懒+我菜QAQ)
5、然后去请教了同机房的RHL同学,学会了另一种做法:map+struct(结构体),在Ta的指导下A了这个道题(我还是太蒻了)
接下来具体介绍一下map+struct的做法
解题思想:
PS;可能不太好理解,请耐心阅读,看了后面的“具体做法”+代码应该会好点qwq(大佬请忽略)
1、对于每一行输入,将前面的前序任务单独存储在beg中
2、然后依次读取后面的后续任务,存储在task里面
3、每读取完一个task,就又存储在map中并进行标序(敲黑板!序号就是map的映射值)
4、但是map本身无法根据映射值进行排序,所以我们费尽心思想到再用struct来解决:每个struct存任务的名字和对应的map序号,再根据map序号进行快排
具体做法:
1、输入一行字符串就对这行进行solve处理(solve自定义函数后面会讲)
2、定义一个map<string,int> shan来记录顺序,规则如下:(划重点)shan[task]=shan[beg]+1。因为task表示后续任务,beg是前序任务,所以task的顺序直接在beg的顺序之上依次往后移一位即可
3、通过迭代器遍历map数组,将每一个任务的名字、map值转移到struct里面存储
4、自定义cmp快排,将struct按照map值从小到大排序,最后输出
代码理解:
#include <bits/stdc++.h>
using namespace std;
int n,k;
string s,beg,task;
map<string,int> shan;
struct node {
int lev; //存储每个任务的map值和名字
string name;
}a[100001];
void solve(string p) { //处理每行字符串
int f=p.find('('),len=p.length(); //f记录第一次出现'('的位置,len是字符串长度
beg.clear(); //清空好习惯qwq
for(register int i=0;i<f;i++) { //将前序任务存储到beg中
beg+=p[i]; //@@@
}
task.clear();
for(register int i=f+1;i<len;i++) { //开始依次处理每个前序任务对应的后续任务
if(p[i]=='N') break;
if(p[i]==','||p[i]==')') { //一个任务读取完了
shan[task]=shan[beg]+1; //map值++,即顺序往后排
task.clear(); //一定要清空
}
else task+=p[i]; //@@@
}
}
bool cmp(node x,node y) { //根据每个任务的map值来从小到大排序
if(x.lev==y.lev) return x.name<y.name;
else return x.lev<y.lev;
}
int main() {
scanf("%d",&n);
for(register int i=1;i<=n;i++) { //边读入边处理
cin>>s;
solve(s);
}
for(map<string,int>::iterator it=shan.begin();it!=shan.end();it++) { //通过迭代器遍历map
//cout<<it->first<<" "<<it->second<<endl; 可以检查一下map部分的处理是否正确
a[++k].name=(it->first); //将信息保存在struct中
a[k].lev=(it->second);
}
sort(a+1,a+1+k,cmp);
for(register int i=1;i<=k;i++) cout<<a[i].name<<" ";
return 0;
}
注意一下:
“@@@”的地方,字符串转移直接相加即可(如上代码所示),不能写成“beg[i]=p[i]”,我就因为这里白瞎盯着程序找了好久错QAQ(就是菜啊)
尾声:
可能这种做法还有很多不足和需要优化的地方,敬请各位大佬指出。写篇题解,权当提供一种新思路,大家一起进步呀qwq