题意:有多个任务,每个任务有需要花费的时间和最后期限,任务之间也有一些先后关系,必须先完成某个才能开始某个,对于每个任务,如果没有越期,则超时为0,否则超时为结束时间-最后期限,求超时时间最大值最小的任务顺序。
由于完成这些任务的总时间是一样的,所以只要贪心地尽量取结束时间早的先做就行,只不过加上了拓扑序的限制,就将任务按结束时间排大小,拓扑序做就行了。
1 #include<stdio.h>
2 #include<string.h>
3 #include<queue>
4 using namespace std;
5
6 const int maxn=5e4+5;
7 const int maxm=5e5+5;
8
9 struct job{
10 int p,d,id,num;
11 bool operator < (const job a)const{
12 return d<a.d;
13 }
14 }w[maxn];
15
16 int head[maxn],point[maxm],nxt[maxm],size;
17 int n;
18
19 void init(){
20 memset(w,0,sizeof(w));
21 memset(head,-1,sizeof(head));
22 size=0;
23 for(int i=1;i<=n;++i)w[i].num=i;
24 }
25
26 void add(int a,int b){
27 point[size]=b;
28 nxt[size]=head[a];
29 head[a]=size++;
30 w[b].id++;
31 }
32
33 void topo(){
34 priority_queue<job>q;
35 for(int i=1;i<=n;++i)if(!w[i].id)q.push(w[i]);
36 while(!q.empty()){
37 job u=q.top();
38 q.pop();
39 int s=u.num;
40 printf("%d
",s);
41 for(int i=head[s];~i;i=nxt[i]){
42 int j=point[i];
43 w[j].id--;
44 if(!w[j].id)q.push(w[j]);
45 }
46 }
47 }
48
49 int main(){
50 while(scanf("%d",&n)!=EOF){
51 init();
52 for(int i=1;i<=n;++i){
53 scanf("%d%d",&w[i].p,&w[i].d);
54 }
55 int m;
56 scanf("%d",&m);
57 while(m--){
58 int a,b;
59 scanf("%d%d",&a,&b);
60 add(a,b);
61 }
62 topo();
63 }
64 return 0;
65 }
之前写的是总超时时间最小的任务顺序……其实笔误了,不过并没有人告知23333自己后来看的时候才发现写错了,不过A这道题的时候并没有想错