链路可靠性

在这里插入图片描述

思路

建图，dfs
我这里是用的哈希表，加数组的形式，也差不多

import java.util.*;
public class Main{static class Node{int target;int weight;public Node(int t, int w){target = t;weight = w;}}static Map<Integer, ArrayList<Node>> map;public static void main(String[] args){Scanner sc = new Scanner(System.in);map = new HashMap<>();while(sc.hasNext()){int start = sc.nextInt();int target = sc.nextInt();int weight = sc.nextInt();Node node = new Node(target, weight);ArrayList<Node> list = map.getOrDefault(start, new ArrayList<>());list.add(node);map.put(start, list);}int res = 0;Main main = new Main();for(int key : map.keySet()){int len = main.dfs(key, 0);res = Math.max(res, len);}System.out.println(res);}public int dfs(int start, int len){if(!map.containsKey(start)) {return len;}int res = 0;ArrayList<Node> list = map.get(start);for(int i = 0; i < list.size(); i++){Node node = list.get(i);int t = node.target;int w = node.weight;res = Math.max(res, dfs(t,len + w));}return res;}
}

同时运行的出租车数量

在这里插入图片描述

思路

就是遍历时间，看这个时间有没有车经过
注意路是环形的，两地经过的时间要处理一下

import java.util.*;
public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int N = sc.nextInt();int K = sc.nextInt();int[][] person = new int[K][3];int res = 0;for(int i = 0; i < K; i++){person[i][0] = sc.nextInt();person[i][1] = sc.nextInt();person[i][2] = sc.nextInt();}for(int i = 0; i <= 1000; i++){int temp = 0;for(int j = 0; j < K; j++){int pos1 = person[j][1];int pos2 = person[j][2];int diff = Math.abs(pos1 - pos2);int num = Math.min(diff, N - diff);if(person[j][0] <= i && i < person[j][0] + num * 5)temp++;}res = Math.max(res, temp);}System.out.println(res);}
}

生产调度

在这里插入图片描述

思路

第二三次周赛时候的题吧，忘记了，第三道，当时有bug没发现
思路就是两个优先队列，一个放工序，一个放设备（记录用完的时间）
然后遍历时间，根据当前是否有设备，是否到达了完工时间来处理逻辑

import java.util.*;
public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int N = sc.nextInt();int K = sc.nextInt();int[][] shebei = new int[K][2];PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]));for(int i = 0; i < K; i++){shebei[i][0] = sc.nextInt();shebei[i][1] = sc.nextInt();pq.offer(shebei[i]);}int res = 0;PriorityQueue<Integer> time = new PriorityQueue<>();int num = 0;//遍历时间for(int i = 0; i < 1000 * 1000; i++) {if(pq.isEmpty())break;//如果到点了，机器停止while(!time.isEmpty() && time.peek() == i){time.poll();}//如果机器没有空闲,剪枝if(time.size() == N){i = time.peek() - 1;}while(!pq.isEmpty() && time.size() < N){int[] temp = pq.poll();time.offer(i + temp[0]);res = Math.max(res, i + temp[0]);}}System.out.println(res);}
}