题目解析

在无线用户管理系统中，一个用户的呼叫流程称为一个 task，由多个子流程 (Procedure) 组成。每个 Procedure 可以嵌套调用其他 Procedure，甚至可以递归调用自身。为了优化系统性能，需要计算每个 Procedure 的实际执行时间，即不包括子 Procedure 执行时间的部分。如果一个 Procedure 被多次调用，应输出其最长的执行时间。

问题要点

1. 嵌套调用与递归调用：需要使用栈来模拟 Procedure 的调用和返回过程。
2. 多次调用：同一个 Procedure 可能被多次调用，每次调用的执行时间可能不同，需记录每次调用的执行时间，并取最大值。
3. 时间戳处理：日志中的时间戳是严格递增的，且每个 Procedure 的执行时间至少为1。

解题思路

1. 使用栈模拟调用过程：

   • 使用一个栈来跟踪当前正在执行的 Procedure。栈顶元素表示当前正在执行的 Procedure。
   • 每当遇到一个入口日志 (type = 0)，将其压入栈，并记录开始时间。
   • 每当遇到一个出口日志 (type = 1)，弹出栈顶的 Procedure，计算其执行时间，并将其从当前执行时间中扣除子 Procedure 的执行时间。

2. 记录执行时间：

   • 使用一个数组 execTime[m] 来记录每个 Procedure 的最长执行时间。
   • 对于每个 Procedure，在每次调用结束时，更新其最长执行时间。

3. 处理时间戳：

   • 使用一个变量 prev 来记录上一个时间点，以便计算当前 Procedure 的实际执行时间。

4. 处理递归调用与多次调用：

   • 由于 Procedure 可以递归调用自身或多次调用，因此需要对每次调用分别处理，并记录各自的执行时间。

cpp

#include <bits/stdc++.h>
using namespace std;

// 定义一个结构体来表示栈中的每个Procedure调用
struct Proc {
    int id;                 // Procedure编号
    long long lastStart;    // 上一次开始执行的时间
    long long exclusiveTime; // 当前调用的实际执行时间
};

int main(){
    int m, n;
    cin >> m >> n;
    // 初始化每个Procedure的最长执行时间为0
    long long execTime[m];
    memset(execTime, 0, sizeof(execTime));
    // 使用栈来模拟Procedure的调用
    stack<Proc> s;
    long long prev = 0; // 上一个时间点
    while(n--){
        int id, type;
        long long time;
        cin >> id >> type >> time;
        if(type == 0){
            // 入口日志
            if(!s.empty()){
                // 当前栈顶Procedure被新的Procedure打断，累计其执行时间
                s.top().exclusiveTime += (time - s.top().lastStart);
            }
            // 压入新的Procedure调用
            Proc newProc;
            newProc.id = id;
            newProc.lastStart = time;
            newProc.exclusiveTime = 0;
            s.push(newProc);
        }
        else{
            // 出口日志
            if(s.empty()){
                // 异常情况，出口日志但栈为空
                continue;
            }
            // 弹出当前Procedure
            Proc finishedProc = s.top(); s.pop();
            // 计算当前Procedure的执行时间
            finishedProc.exclusiveTime += (time - finishedProc.lastStart + 1);
            // 更新最长执行时间
            execTime[finishedProc.id] = max(execTime[finishedProc.id], finishedProc.exclusiveTime);
            if(!s.empty()){
                // 父Procedure恢复执行，更新时间
                s.top().lastStart = time + 1;
            }
        }
    }
    // 输出每个Procedure的最长执行时间
    for(int i=0;i<m;i++) cout << execTime[i] << (i<m-1?" ":"\n");
    return 0;
}

python

m, n = map(int, input().split())
execTime = [0] * m
stack = []
for _ in range(n):
    id, type, time = map(int, input().split())
    if type == 0:
        # 入口日志
        if stack:
            # 当前栈顶Procedure被新的Procedure打断，累计其执行时间
            stack[-1]['exclusiveTime'] += (time - stack[-1]['lastStart'])
        # 压入新的Procedure调用
        stack.append({'id': id, 'lastStart': time, 'exclusiveTime': 0})
    else:
        # 出口日志
        if not stack:
            continue  # 异常情况，出口日志但栈为空
        finishedProc = stack.pop()
        # 计算当前Procedure的执行时间
        finishedProc['exclusiveTime'] += (time - finishedProc['lastStart'] +1)
        # 更新最长执行时间
        execTime[finishedProc['id']] = max(execTime[finishedProc['id']], finishedProc['exclusiveTime'])
        if stack:
            # 父Procedure恢复执行，更新时间
            stack[-1]['lastStart'] = time +1
# 输出结果
print(' '.join(map(str, execTime)))

java

import java.util.*;
public class Main {
    // 定义一个内部类来表示栈中的每个Procedure调用
    static class Proc {
        int id;                 // Procedure编号
        long lastStart;         // 上一次开始执行的时间
        long exclusiveTime;     // 当前调用的实际执行时间

        Proc(int id, long lastStart) {
            this.id = id;
            this.lastStart = lastStart;
            this.exclusiveTime = 0;
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        long[] execTime = new long[m];
        Stack<Proc> stack = new Stack<>();
        for(int i=0;i<n;i++){
            int id = sc.nextInt();
            int type = sc.nextInt();
            long time = sc.nextLong();
            if(type == 0){
                // 入口日志
                if(!stack.isEmpty()){
                    // 当前栈顶Procedure被新的Procedure打断，累计其执行时间
                    Proc topProc = stack.peek();
                    topProc.exclusiveTime += (time - topProc.lastStart);
                }
                // 压入新的Procedure调用
                stack.push(new Proc(id, time));
            }
            else{
                // 出口日志
                if(stack.isEmpty()){
                    continue; // 异常情况，出口日志但栈为空
                }
                Proc finishedProc = stack.pop();
                // 计算当前Procedure的执行时间
                finishedProc.exclusiveTime += (time - finishedProc.lastStart +1);
                // 更新最长执行时间
                execTime[finishedProc.id] = Math.max(execTime[finishedProc.id], finishedProc.exclusiveTime);
                if(!stack.isEmpty()){
                    // 父Procedure恢复执行，更新时间
                    stack.peek().lastStart = time +1;
                }
            }
        }
        // 输出每个Procedure的最长执行时间
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<m;i++) {
            sb.append(execTime[i]);
            if(i < m-1) sb.append(" ");
            else sb.append("\n");
        }
        System.out.print(sb.toString());
    }
}

题目内容

无线用户管理系统中，一个用户呼叫流程称为一个 $task$ ，$task$ 由若干个子流程($Procedure$)组成，$Procedure$ 可以继续调用更小粒度的 $Procedure$ ; $task$ 是呼叫流程的入口，也是一种特殊的Procedure。

为了对呼叫流程处理性能进行优化分析，调度框架在每个 $Procedure$ 的入口和出口记录了系统时间戳的日志。现在需要你根据日志信息分析得到每个 $Procedure$ 的实际执行时间(不包括子 $procedure$ 的执行时间)。

备注:

1. $Procedure$可以被调用多次，也可以被递归调用;

2. $Procedure$ 的入口记录表示 $Procedure$ 从记录时间戳的起始开始执行出口记录表示 $Procedure$ 在记录时间截的末尾结束执行;

3. $Procedure$ 的日志时间截至少间隔1

4. 如果同一个 $procedure$ 多次调用且执行时间不相同，请输出最长的执行时间。

输入描述

第一行输入 $Procedure$ 的个数 $m$ 和日志记录个数，以空格隔开。$m$ 取值范围 $[1,100]$，$n$ 取值范围 $[2,500]$ ;

后面的 $n$ 行输入日志记录，每条日志由 $3$ 个整数组成并以空格隔开。日志格式: $Procedure$ 编号(取值范围:$[0,m)$),日志类型(入口: $0$，出口: $1$ )，时间戳(取值范围:$[0,1000000000]$)

输出描述

以 $Procedure$ 编号顺序输出每个 $Procedure$ 的实际执行时间(不包括子 $procedure$ 的执行时间)，以空格隔开;

样例1

输入

2 6
0 0 0
1 0 2
1 1 5
1 0 6
1 1 9
0 1 10

输出

3 4

说明

如上图:

$Procedure0$ 在时间戳 $0$ 的开始执行，执行 $2$ 个单位时间，于时间戳 $1$ 的未尾结束执行。

$Procedure1$ 在时间戳 $2$ 的开始执行，执行 $4$ 个单位时间，于时间戳 $5$ 的末尾结束执行。

$Procedure1$ 在时间戳 $6$ 的开始再次执行，执行 $4$ 个单位时间，于时间戳 $9$ 的末尾结束执行。

$Procedure0$ 在时间戳 $10$ 的开始恢复执行，执行 $1$ 个单位时间。

所以 $Procedure0$ 总共执行 $2+1=3$ 个单位时间，$Procedure1$ 总共执行 $4$ 个单位时间。

样例2

输入

2 6
0 0 0
1 0 2
1 0 5
1 1 10
1 1 11
0 1 12

输出

3 6

说明

$Procedure0$ 在时间戳 $0$ 的开始执行，执行 $2$ 个单位时间，于时间戳 $1$ 的末尾结束执行。

$Procedure1$ 在时间戳 $2$ 的开始执行，执行 $3$ 个单位时间，于时间戳 $4$ 的末尾结束执行。

$Procedure1$ 在时间戳 $5$ 的开始递归调用自己(记为 $Procedure 1$')执行 $6$ 个单位时间，于时间戳 $10$ 的末尾结束执行。

$Procedure1$ 在时间戳 $11$ 的开始恢复执行，执行 $1$ 个单位时间。

$Procedure0$ 在时间 $12$ 的开始恢复执行，执行 $1$ 个单位时间。

所以 $Procedure0$ 总共执行 $2+1=3$ 个单位时间，$Procedure1$总共执行 $3+1=4$ 个单位时间。$Procedure1'$总共执行 $6$ 个单位时间。所以 $Procedure 1$ 取最大的执行时间即 $5$ .