阿里3.26笔试第二题——酒店的平均距离

阿里3.26日笔试第二题。我没有参加笔试,但是听人说是2020年威海站的题,就按照威海站做的。时间复杂度最高达到O(n^4),欢迎有好的优化思路的小伙伴在评论区留言,欢迎收藏与转发。
package Algorithms.AL.AL010;

import java.util.Scanner;

/**
 * 题目描述
 *      三名理论计算机科学家计划前往威海旅行。 但是,他们无法就住宿达成共识,因为有些人喜欢某些酒店,
 *      而另一些人则喜欢其他酒店。 他们决定晚上住在不同的旅馆里,第二天在一个旅馆见面。
 *      他们见面的酒店不一定是他们入住的酒店之一。
 *      每对酒店之间都有一条特定长度的道路,每位理论计算机科学家都会在旅行开始之前准备好候选酒店列表。
 *      当他们到达威海时,他们每个人都会从候选酒店列表中统一独立地选择一家酒店。
 *      而且,他们将在一家酒店见面,以使他们的路线总长度最小化。
 *      作为理论计算机科学小组的成员,您能说出他们的路线的预期总长度吗?
 *
 * 输入描述
 *      输入的第一行包含一个整数 n(1≤ n ≤200000),表***海的酒店数量。
 *      接下来 n-1 行中的每行都包含三个整数 u,v,w(1≤u,v≤n,u≠v,1≤w≤1000),
 *      表示长度为 w 的道路,连接编号为 u 和 v 的旅馆。
 *      保证每对酒店之间都有一条独特的道路。
 *      输入的最后三行指定候选酒店列表,每位理论计算机科学家一行。
 *      每行有一个整数 m(1≤ m ≤n)和 m 个不同的整数 a1,a2,⋯,am(1≤ ai ≤n),这意味着候选酒店列表为编号为 a1,a2,⋯,的酒店。
 *
 * 输出描述
 *      输出所有情况下最短总路程的平均值
 *
 * 示例1
 *      输入
 *      3
 *      1 2 1
 *      2 3 2
 *      1 1
 *      1 2
 *      1 3
 *      输出
 *      3
 *
 * 示例2
 *      输入
 *      5
 *      1 2 3
 *      1 3 5
 *      2 4 7
 *      2 5 11
 *      3 2 4 5
 *      4 1 2 3 5
 *      2 1 3
 *      输出
 *      13.958333333333
 *
 */
public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {
            // 获取酒店数量
            int n = scanner.nextInt();
            // 构建酒店之间直接距离矩阵
            int[][] distances = new int[n][n];
            // 将直接距离初始化为 Integer.MAX_VALUE,表示各个酒店之间没有连接
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    distances[i][j] = Integer.MAX_VALUE;
                }
            }
            // 同一酒店与自己的距离当然为 0
            for (int i = 0; i < n; i++) {
                distances[i][i] = 0;
            }
            // 接下来 n-1 行,获取每两个酒店 u 和 v 之间的直接距离 w
            for (int i = 0; i < n-1; i++) {
                int u = scanner.nextInt()-1;
                int v = scanner.nextInt()-1;
                int w = scanner.nextInt();

                distances[u][v] = distances[v][u] = w;
            }
            // 利用 Floyed 算法计算每两个酒店之间的最短距离
            for (int t = 0; t < n; t++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (distances[i][t] < Integer.MAX_VALUE && distances[t][j] < Integer.MAX_VALUE
                            && distances[i][t] + distances[t][j] < distances[i][j]) {
                            distances[i][j] = distances[i][t] + distances[t][j];
                        }
                    }
                }
            }

            // 接下来获取三名科学家每个人喜欢的酒店编号
            // 第一名科学家喜欢的酒店数量
            int num1 = scanner.nextInt();
            // 第一名科学家喜欢的酒店编号
            int[] favorite1 = new int[num1];
            for (int i = 0; i < num1; i++) {
                favorite1[i] = scanner.nextInt()-1;
            }
            // 第二名科学家喜欢的酒店数量
            int num2 = scanner.nextInt();
            // 第二名科学家喜欢的酒店编号
            int[] favorite2 = new int[num2];
            for (int i = 0; i < num2; i++) {
                favorite2[i] = scanner.nextInt()-1;
            }
            // 第三名科学家喜欢的酒店数量
            int num3 = scanner.nextInt();
            // 第三名科学家喜欢的酒店编号
            int[] favorite3 = new int[num3];
            for (int i = 0; i < num3; i++) {
                favorite3[i] = scanner.nextInt()-1;
            }

            // 三名科学家一共有 num1*num2*num3 种不同组合
            int nums = num1*num2*num3;
            // 设置总路径
            int sum = 0;
            // 获取每种情况下的最短路径
            for (int i = 0; i < num1; i++) {
                for (int j = 0; j < num2; j++) {
                    for (int k = 0; k < num3; k++) {
                        // 计算最小值
                        int min = Integer.MAX_VALUE;
                        for (int v = 0; v < n; v++) {
                            min = Math.min(min, distances[favorite1[i]][v] + distances[favorite2[j]][v] + distances[favorite3[k]][v]);
                        }
                        sum += min;
                    }
                }
            }

            // 输出统计结果
            System.out.println(sum*1.0/nums);
        }
    }
}


#笔试题目##阿里巴巴#
全部评论
不加证明地猜测求最短路径时直接取两两距离总和的一半,这样就能优化到n^3数量级了
1 回复
分享
发布于 2021-04-06 11:34
将方案数和距离和分开计算,方案数用容斥算,距离和就枚举树上的每条边,讨论将3个人分成两边的3种情况分别计算方案数,这条边对距离和的贡献为这条边的长度乘以总方案数,最后期望为距离和除以方案数,时空复杂度O(n)。
1 回复
分享
发布于 2021-04-06 22:38
乐元素
校招火热招聘中
官网直投

相关推荐

点赞 评论 收藏
转发
点赞 10 评论
分享
牛客网
牛客企业服务