拼多多服务端开发笔试第3题

import java.util.*;  public class Third { /**  5 6  1 2 1 1 1  1 2  1 3  1 4  2 5  3 5  4 5  */  /**  * 任务->被依赖任务 默认为空  */  private static Map<Integer, Set<Integer>> maps = new HashMap<>();  /**  * 任务->依赖任务  */  private static Map<Integer, Set<Integer>> tasks = new HashMap<>();  /**  * 已访问结点  */  private static Set<Integer> visited = new HashSet<>();   public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  int n = sc.nextInt();  int m = sc.nextInt();  // 服务时间  int[] data = new int[n + 1];  data[0] = 0;   int first = 0;  // 读入数据  while (first < n) {
            data[++first] = sc.nextInt();  Set<Integer> set = new HashSet<>();  maps.put(first, set);  } // 任务依赖信息  int second = 0;  while (second < m) { int a = sc.nextInt();  int b = sc.nextInt();  // 被依赖映射  Set<Integer> set = maps.get(a);  set.add(b);  // 依赖映射  if (tasks.containsKey(b)) {
                Set<Integer> others = tasks.get(b);  others.add(a);  } else {
                Set<Integer> others = new HashSet<>();  others.add(a);  tasks.put(b, others);  }
            second++;  }
        System.out.println(maps);  System.out.println(tasks);  // 按服务时间大小排序  int[] indexes = mergeSortToIndicesASC(data);  System.out.println(Arrays.toString(indexes));  // 已处理结点数  int count = 1;  int countSum = 0;  // 处理到结点i总的等待时间  int[] wait = new int[n + 1];  wait[0] = 0;  // 任务安排  int[] res = new int[n + 1];  res[0] = 0;  // 处理任务  while (count <= n) { for (int i = 1; i <= n; i++) { if (!visited.contains(indexes[i])) {
                    Set<Integer> numberTask = tasks.get(indexes[i]);  if (numberTask == null || numberTask.isEmpty()) {
                        res[count] = indexes[i];  // 依赖项发生改变  remove(maps, tasks, indexes[i]);  visited.add(indexes[i]);  countSum = countSum + wait[count - 1] + data[indexes[i]];  wait[count] = wait[count - 1] + data[indexes[i]];  count++;  break;  }
                }
            }
        } for (int i = 1; i < res.length; i++) { if (i > 1) {
                System.out.print(" ");  }
            System.out.print(res[i]);  }
        System.out.println();  System.out.println(Arrays.toString(wait));  System.out.println(countSum * 1.0 / n);  } public static void remove(Map<Integer, Set<Integer>> maps, Map<Integer, Set<Integer>> tasks, int task) {
        Set<Integer> others = maps.get(task);  Iterator<Integer> iterator = others.iterator();  while (iterator.hasNext()) { int other = iterator.next();  tasks.get(other).remove(task);  }
    } public static int[] mergeSortToIndicesASC(int[] paraArray) { int tempLength = paraArray.length;  int[][] resultMatrix = new int[2][tempLength];   // Initialize  int tempIndex = 0;  for (int i = 0; i < tempLength; i++) {
            resultMatrix[tempIndex][i] = i;  }// Of for i  // Merge  int tempCurrentLength = 1;  // The indices for current merged groups.  int tempFirstStart, tempSecondStart, tempSecondEnd;  while (tempCurrentLength < tempLength) { // Divide into a number of groups  // Here the boundary is adaptive to array length not equal to 2^k.  for (int i = 0; i < Math.ceil(tempLength + 0.0 / tempCurrentLength) / 2; i++) { // Boundaries of the group  tempFirstStart = i * tempCurrentLength * 2;  tempSecondStart = tempFirstStart + tempCurrentLength - 1;  if (tempSecondStart >= tempLength) { break;  }// Of if  tempSecondEnd = tempFirstStart + tempCurrentLength * 2 - 1;  if (tempSecondEnd >= tempLength) {
                    tempSecondEnd = tempLength - 1;  }// Of if   // Merge this group  int tempFirstIndex = tempFirstStart;  int tempSecondIndex = tempSecondStart + 1;  int tempCurrentIndex = tempFirstStart;  while ((tempFirstIndex <= tempSecondStart)
                        && (tempSecondIndex <= tempSecondEnd)) { if (paraArray[resultMatrix[tempIndex % 2][tempFirstIndex]] <= paraArray[resultMatrix[tempIndex % 2][tempSecondIndex]]) {
                        resultMatrix[(tempIndex + 1) % 2][tempCurrentIndex] = resultMatrix[tempIndex % 2][tempFirstIndex];  tempFirstIndex++;  } else {
                        resultMatrix[(tempIndex + 1) % 2][tempCurrentIndex] = resultMatrix[tempIndex % 2][tempSecondIndex];  tempSecondIndex++;  }// Of if  tempCurrentIndex++;  }// Of while   // Remaining part  for (int j = tempFirstIndex; j <= tempSecondStart; j++) {
                    resultMatrix[(tempIndex + 1) % 2][tempCurrentIndex] = resultMatrix[tempIndex % 2][j];  tempCurrentIndex++;  }// Of for j  for (int j = tempSecondIndex; j <= tempSecondEnd; j++) {
                    resultMatrix[(tempIndex + 1) % 2][tempCurrentIndex] = resultMatrix[tempIndex % 2][j];  tempCurrentIndex++;  }// Of for j  }// Of for i  tempCurrentLength *= 2;  tempIndex++;  }// Of while  return resultMatrix[tempIndex % 2];  }// Of mergeSortToIndices