2022.11.03-秋招-第二题-指令排序

ID: 36

Tried: 166

Accepted: 47

Difficulty: 6

题目内容

塔子哥最近在做一个工程，工程里面有很多的指令，假设指令 $A$ ： $a= 1$ ；指令 $B$ ： $b=2\times a$ ；

$A$ 指令define了变量 $a$ ， $B$ 指令 $use$ 了变量 $a$ , 我们称 $A$ 为 $PRO(producer)$ ， $B$ 为 $CON (consumer)$ ，他们之间的延时称为 $latency$

若 $A$ 和 $B$ 之间有多条依赖，取最大的 $Iatency$ , $PRIORITY (A)$ 表示指令 $A$ 的优先级，其计算公式如下： $PRIORITY(A)= PRIORITY(B) + latency$ ；

若 $A$ 有多个 $CON (B1, B2)$ ，其 $lategcy$ 分别为 $(L1,L2)$ ： $PRIORITY(A)= max (PRIORITY(B1)+ L1, PRIORITY(B2)+L2)$ ；

若 $A$ 没有 $CON$ : $PRIORITY(A)=0$ ；

现有若干条指令(数据依赖没有环)，编号分别为 $1,2,...,n$ 现需要根据其 $PRIORITY$ 对其进行排序，若两条指令的 $PRIORITY$ 相同，则根据其编号先后进行排序。

输入描述

第一行：指令数 $n$ (最大不超过 $100$ )，关系行数 $m$ (最大不超过 $500$ )

第 $2 一m+1$ 行： $PRO-CON$ 关系，如 $(1\ 2\ 4)$ 表示编号 $1$ 和编号 $2$ 指令存在 $PRO-CON$ 关系，其 $latency=4$

输出描述

输出最终的排序编号： $1\ 2\ 3$

样例

样例一：

输入

输出

1 2 3 4

样例二：

输入

输出

3 1 2

题目大意

给定若干条指令（最多 100 条），每条指令可能依赖于其他指令。指令之间的依赖关系用 PRO-CON 关系表示，其中 PRO 表示生产者指令，CON 表示消费者指令，依赖的延迟时间（latency）也随之给出。任务是计算每条指令的优先级，并根据优先级进行排序

题目思路

这道题主要涉及拓扑排序和动态规划的结合应用。具体步骤如下：

1.建立图模型：

将每条指令看作图中的一个节点。 PRO-CON 关系看作有向边，从 PRO 指令指向 CON 指令。每条边带有一个权重，表示延时。

2.拓扑排序：

由于指令依赖关系形成了一个有向无环图（DAG），可以对图进行拓扑排序。拓扑排序的目的是确保所有指令按照依赖关系的顺序执行。

3.动态规划计算优先级：

初始化每条指令的优先级为 0。按照拓扑排序的顺序处理每个节点：对于每个 CON 指令，根据其所有 PRO 指令的优先级和延时，更新其优先级为所有可能值中的最大值。具体地，对于每条边 u -> v，更新 PRIORITY(v) = max(PRIORITY(v), PRIORITY(u) + L)。 4.排序指令：

根据计算得到的优先级对指令进行排序。优先级高的指令排在前面。如果优先级相同，则编号小的指令排在前面。

整道题可以说是DAG动态规划的板子题，也是拓扑排序的板子题。不理解的话可以去搜索一下复习一下。

代码说明

代码整体流程

1.输入读取：

从标准输入读取指令的数量 n（总指令数）和关系的数量 m（依赖关系数）。接着，读取接下来的 m 行，每行的格式为 (u, v, latency)，表示指令 u 依赖于指令 v，并且有一定的延迟时间。

2.初始化变量：

创建一个邻接表或动态数组 edge，用于存储每条指令的依赖关系。初始化一个数组 ans，用于记录每条指令的优先级和对应的编号。还需要一个数组 in，用于记录每个指令的入度，表示有多少条指令依赖于该指令。

3.构建图：

遍历输入的依赖关系，更新邻接表，记录每条指令的消费者和对应的延迟。同时更新入度数组，记录每条指令被多少其他指令依赖。

4.拓扑排序：

使用队列实现拓扑排序，将所有入度为 0 的指令入队，并初始化这些指令的优先级为 0。接下来，进行广度优先搜索（BFS），不断从队列中取出指令，更新其消费者的优先级，并减少消费者的入度。

5.优先级计算：

在处理每条指令时，根据依赖关系和延迟时间更新消费者的优先级。对于每个消费者，优先级的计算规则是：优先级(v) = 最大值(优先级(u) + 延迟)。在这个过程中，维护优先级数组，记录每条指令的最大优先级和对应的编号。

6.排序结果：

使用排序算法对优先级数组进行排序。首先按优先级从高到低排序，如果优先级相同，则按指令编号升序排序。

7.输出结果：

遍历排序后的优先级数组，输出每条指令的编号（根据需要调整索引），形成最终的排序结果。

代码

Java代码

import java.util.*;

public class Main {
    static class Edge{//记录边
        public int to;
        public int val;
        Edge(int a, int b){
            to = a;
            val = b;
        }
        Edge(){}
    }
    static class Value{//记录我们最后的答案统计
        public int val1 = 0;
        public int val2 = 0;
        Value(int a, int b){
            val1 = a;
            val2 = b;
        }
        Value(){val1 = val2 = 0;}
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        //二维数组用于存储边，第一位是固定数组，第二维是动态数组
        ArrayList<Edge>[] edge = new ArrayList[n];
        Value[] ans = new Value[n];//记录我们的答案，最后需要排序
        int[] in = new int[n];//拓扑排序的要点，记录一个点的入度
        for(int i = 0; i < n; i++){//初始化
            edge[i] = new ArrayList<Edge>();
            ans[i] = new Value();
        }

        for (int i = 1; i <= m; i++){
            int u = input.nextInt();
            int v = input.nextInt();
            int val = input.nextInt();
            u--;
            v--;
            edge[v].add(new Edge(u, val));//加边
            in[u]++;//加度
        }
        Queue<Integer> q = new LinkedList<Integer>();//拓扑排序bfs版，需要队列
        for(int i = 0; i < n; i++){
            if(in[i] == 0){
                q.offer(i);//度数为0的直接压进队列
                ans[i] = new Value(0, i);//答案数记为(0,i),0是他的latency，i是编号
            }
        }
        while(!q.isEmpty()){
            int u = q.poll();//队列非空的时候不断取点
            for(int i = 0; i < edge[u].size(); i++){
                int v = edge[u].get(i).to;
                //更新答案，DAG动态规划的核心步骤
                ans[v].val1 = Math.max(ans[v].val1, ans[u].val1 + edge[u].get(i).val);
                ans[v].val2 = v;
                in[v]--;//如果度数为0，就压进队列，也是拓扑排序的核心
                if(in[v] == 0)q.offer(v);
            }
        }
        Arrays.sort(ans, new Comparator<Value>() {//排序
            @Override
            public int compare(Value o1, Value o2) {
                if(o1.val1 == o2.val1)return o1.val2 - o2.val2;
                else return o2.val1 - o1.val1;
            }
        });
        for(int i = 0; i < n; i++){//输出答案
            System.out.print(ans[i].val2 + 1);
            if(i != n - 1) System.out.print(" ");
        }
    }
}

C++代码

#include <bits/stdc++.h>
using namespace std;
struct Edge { //记录边
    int to;
    int val;
    Edge(int a, int b) {
        to = a;
        val = b;
    }
    Edge() {}
};

struct Value { //记录我们最后的答案统计
    int val1 = 0;
    int val2 = 0;

    Value(int a, int b) {
        val1 = a;
        val2 = b;
    }
    Value() {val1 = val2 = 0;}
    bool operator<(Value b)	//排序
    {
        return val1!=b.val1?val1>b.val1:val2<b.val2;
    }
};
int in[505];
Value ans[505];
int main()
{
    int n, m;
    cin >> n >> m;
    vector<Edge>edge[505];
    for (int i = 1; i <= m; i++) {
        int u, v, val;
        cin >> u >> v >> val;
        u--;
        v--;
        edge[v].push_back(Edge(u, val));//加边
        in[u]++;//加度
    }
    queue<int>q;
    for (int i = 0; i < n; i++) {
        if (in[i] == 0) {
            q.push(i);//度数为0的直接压进队列
            ans[i] = Value(0, i);//答案数记为(0,i),0是他的latency，i是编号
        }
    }
    while (!q.empty()) {
        int u = q.front();//队列非空的时候不断取点
        q.pop();
        for (int i = 0; i < edge[u].size(); i++) {
            int v = edge[u][i].to;
            //更新答案，DAG动态规划的核心步骤
            ans[v].val1 = max(ans[v].val1, ans[u].val1 + edge[u][i].val);
            ans[v].val2 = v;
            in[v]--;//如果度数为0，就压进队列，也是拓扑排序的核心
            if (in[v] == 0)q.push(v);
        }
    }
    sort(ans,ans+n);
    for(int i = 0; i < n; i++){//输出答案
            cout<<ans[i].val2+1;
            if(i != n - 1) cout<<" ";
        }
    return 0;
}

Python代码

import functools

def cmp(x, y):	#排序
    if x[0] == y[0]:
        return x[1]-y[1]
    return y[0]-x[0]

n, m = map(int, input().split())
edge = [[]for i in range(n)]
in1 = [0]*n
for i in range(m):
    u, v, val = map(int, input().split())
    u -= 1
    v -= 1
    edge[v].append([u, val])	#加边
    in1[u] += 1	#加度
q = []
ans = [[0, 0] for i in range(n)]
for i in range(n):
    if (in1[i] == 0):
        q.append(i)		#度数为0的直接压进队列
        ans[i] = [0, i]	#答案数记为(0,i),0是他的latency，i是编号
while (len(q) > 0):
    u = q[0]	#队列非空的时候不断取点
    q.pop(0)
    for now in edge[u]:
        v = now[0]
        #更新答案，DAG动态规划的核心步骤
        ans[v][0] = max(ans[v][0], ans[u][0] + now[1])
        ans[v][1] = v
        in1[v] -= 1	
        if (in1[v] == 0):	#如果度数为0，就压进队列，也是拓扑排序的核心
            q.append(v)
ans.sort(key=functools.cmp_to_key(cmp))
for i in range(n):
    if i != n-1:
        print(ans[i][1]+1, end=" ")
    else:
        print(ans[i][1]+1)

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';

process.stdin.on('data', (data) => {
	input += data;
	return;
});
process.stdin.on('end', () => {
	function cmp(x, y) {	//排序
		if (x[0] == y[0])
			return x[1] - y[1];
		return y[0] - x[0];
	}
	input = input.split('\n');
	let n = Number(input[0].split(' ')[0]);
	let m = Number(input[0].split(' ')[1]);
	let edge = new Array(n);
    for (let i=0;i<n;i++)
        edge[i]=new Array();
	let in1 = new Array(n).fill(0);
	for (let i = 0; i < m; i++) {
		tmp = input[i + 1].split(' ').map(Number);
		u = tmp[0];
		v = tmp[1];
		val = tmp[2];
		u -= 1;
		v -= 1;
		edge[v].push([u, val]);	//加边
		in1[u]++;	//加度
	}
	let q = [];
	let ans = new Array(n);
    for (let i=0;i<n;i++)
        ans[i]=new Array(2).fill(0);
	for (let i = 0; i < n; i++) {
		if (in1[i] == 0) {
			q.push(i);	//度数为0的直接压进队列
			ans[i] = [0, i]	 //答案数记为(0,i),0是他的latency，i是编号
		}
	}
	while (q.length > 0) {
		u = q.shift();	//队列非空的时候不断取点
		edge[u].forEach(element => {
			now = element;
			v = now[0];
            //更新答案，DAG动态规划的核心步骤
			ans[v][0] = Math.max(ans[v][0], ans[u][0] + now[1]);
			ans[v][1] = v;
			in1[v] -= 1;
			if (in1[v] == 0)	//如果度数为0，就压进队列，也是拓扑排序的核心
				q.push(v);
		});
	}
	ans.sort(cmp);
    tmp=[];
	for (let i = 0; i < n; i++)
		tmp.push(ans[i][1] + 1);
    console.log(tmp.join(' '))
})

#P1583. 2022.11.03-秋招-第二题-指令排序