P1113杂务一、题目二、解题思路三、代码

110 阅读 0 评论 73 点赞

我是靠谱客的博主冷傲含羞草，这篇文章主要介绍P1113杂务一、题目二、解题思路三、代码，现在分享给大家，希望可以做个参考。

一、题目

在这里插入图片描述

二、解题思路

这道题难度比较低，双重for循环直接搞定，主要因为题目给的限制条件比较多，降低了题的难度。如果去掉限定条件，杂务k的准备工作只能在杂务1至k-1之间，那题目难度将会适当增大。现在加入限定条件，相当于我们只需要从小到大确定杂务的执行结束时间，但如果取消该条件后，我们每次都需要去寻找，到底哪个杂务的执行结束时间能被确定（即需要找到前驱已经确定的那个杂务）。

三、代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<vector<int>> all_pre(n+1, vector<int>());
    vector<int> finish_time(n+1), costs(n+1);
    int ret;
    for(int i=1;i<=n;i++){
        int id;
        cin>>id;
        int cost;
        cin>>cost;
        costs[i]=cost;
        int pre_task;
        cin>>pre_task;
        while(pre_task){
            all_pre[i].push_back(pre_task);
            cin>>pre_task;
        }
    }
    finish_time[1]=costs[1];
    ret=finish_time[1];
    for(int i=2;i<=n;i++){
        int max_time=0;
        for(int j=0;j<all_pre[i].size();j++){
            max_time=max(max_time, finish_time[all_pre[i][j]]);
        }
        finish_time[i]=max_time+costs[i];
        ret=max(finish_time[i], ret);
    }
    cout<<ret;
}