【每日一练】可信专业级冲冲_java蔬菜配送,求派送完成的最小时间

• 题目：
• 蔬菜配送，求派送完成的最小时间
• 限制：
• 一个小区只能有一个人派送
• 每个人只能派送连续的几个小区
• 输入： 第一行是派送人数，第二行社区数，第三行每个社区所花时间
• 3
• 5
• 1 1 6 3 1
• 结果：
• 一个人派送1+1，一个人派送6，一个人派送3+1，至少耗时6

import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Demo {
    // 待实现函数，在此函数中填入答题代码
    private static int deliver(int num, int[] communities) {
        if (communities.length == 0) {
            return 0;
        }
        // 一、人数多于社区数
        if (num >= communities.length) {
            Arrays.sort(communities);
            return communities[communities.length - 1];
        }

        int max = communities[communities.length - 1];
        // 二、人数少于社区数，进行合并

        // 用链表 合并
        PriorityQueue<Node> nodeQueue = new PriorityQueue<>(Comparator.comparing(node -> node.sumTime));
        Node item = new Node();

        for (int i = 0; i < communities.length - 1; i++) {
            int value = communities[i];
            Node node = new Node(i, value);
            if (value > max) {
                max = value;
            }
            item.next = node;
            item = node;

            node.sumTime = communities[i] + communities[i + 1];
            nodeQueue.add(node);

        }
        item.next = new Node(communities.length - 1, communities[communities.length - 1]);

        int[] merged = new int[communities.length];

        for (int i = 0; i < communities.length - num; ) {
            Node node = nodeQueue.poll();
            //已合并，标记nodeQueue中的节点
            if (merged[node.index] == 1) {
                continue;
            }

            //合并下一个节点
            merged[node.next.index] = 1;

            node.time = node.sumTime;
            node.next = node.next.next;
            if (node.next != null) {
                //刷新，计算下次合并的大小
                node.sumTime = node.sumTime + node.next.time;
            }

            //加回到队列中排序
            nodeQueue.offer(node);

            //耗时，取合并后所有节点的最大值
            max = Math.max(max, node.time);

            i++;
        }
        return max;
    }

    static class Node {
        int index;
        int time;
        //合并下个节点后的大小，用来排序
        int sumTime;
        Node next;

        public Node(int index, int time) {
            this.index = index;
            this.time = time;
        }

        public Node() {
        }
    }

    // main入口
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());
        int num = cin.nextInt();
        int communitiesCnt = cin.nextInt();
        int[] communities = new int[communitiesCnt];
        for (int i = 0; i < communitiesCnt; i++) {
            communities[i] = cin.nextInt();
        }
        cin.close();

        System.out.println(deliver(num, communities));
    }
}


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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102