任务调度 题解

任务调度

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


上一篇:方格取数加强版


下一篇:最大获利