Medium

题目描述

给你一个整数 n，表示国家中城市的数量。城市编号从 0 到 n - 1。

另给你一个二维整数数组 roads，其中 roads[i] = [ai, bi] 表示城市 ai 和 bi 之间存在一条双向道路。

你需要为每个城市分配一个从 1 到 n 的整数值，且每个值只能使用一次。道路的重要性定义为连接的两个城市值的和。

在最优分配值之后，返回所有道路的最大总重要性。

示例 1：

输入：n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：43
解释：上图显示了国家和分配的值 [2,4,5,3,1]。
- 道路 (0,1) 的重要性为 2 + 4 = 6。
- 道路 (1,2) 的重要性为 4 + 5 = 9。
- 道路 (2,3) 的重要性为 5 + 3 = 8。
- 道路 (0,2) 的重要性为 2 + 5 = 7。
- 道路 (1,3) 的重要性为 4 + 3 = 7。
- 道路 (2,4) 的重要性为 5 + 1 = 6。
所有道路的总重要性为 6 + 9 + 8 + 7 + 7 + 6 = 43。
可以证明我们无法获得大于 43 的总重要性。

示例 2：

输入：n = 5, roads = [[0,3],[2,4],[1,3]]
输出：20

约束：

  • 2 <= n <= 5 * 10^4
  • 1 <= roads.length <= 5 * 10^4
  • roads[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 没有重复的道路。

解题思路

这是一个贪心算法问题。关键观察是：每个城市对总重要性的贡献等于该城市的值乘以它的度数（连接的道路数量）。

核心思路：

  1. 统计每个城市的度数（连接的道路数量）
  2. 度数越高的城市，应该分配越大的值
  3. 按度数从小到大排序，然后分配值从1到n

数学分析： 如果城市i的度数为degree[i]，分配的值为value[i]，那么城市i对总重要性的贡献为：degree[i] × value[i]

总重要性 = Σ(degree[i] × value[i])

为了最大化这个和，根据排序不等式，应该让度数大的城市配对大的值。

算法步骤：

  1. 遍历roads数组，统计每个城市的度数
  2. 创建城市编号数组，按度数升序排序
  3. 按排序后的顺序，依次分配值1到n
  4. 计算总重要性：遍历所有道路，累加两端城市值的和

时间复杂度主要在排序环节，整体算法简洁高效。

代码实现

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        vector<int> degree(n, 0);
        
        // 统计每个城市的度数
        for (auto& road : roads) {
            degree[road[0]]++;
            degree[road[1]]++;
        }
        
        // 创建城市索引数组并按度数排序
        vector<int> cities(n);
        iota(cities.begin(), cities.end(), 0);
        sort(cities.begin(), cities.end(), [&](int a, int b) {
            return degree[a] < degree[b];
        });
        
        // 分配值
        vector<int> value(n);
        for (int i = 0; i < n; i++) {
            value[cities[i]] = i + 1;
        }
        
        // 计算总重要性
        long long result = 0;
        for (auto& road : roads) {
            result += value[road[0]] + value[road[1]];
        }
        
        return result;
    }
};

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        # 统计每个城市的度数
        degree = [0] * n
        for a, b in roads:
            degree[a] += 1
            degree[b] += 1
        
        # 按度数排序城市索引
        cities = sorted(range(n), key=lambda x: degree[x])
        
        # 分配值
        value = [0] * n
        for i, city in enumerate(cities):
            value[city] = i + 1
        
        # 计算总重要性
        result = 0
        for a, b in roads:
            result += value[a] + value[b]
        
        return result

public class Solution {
    public long MaximumImportance(int n, int[][] roads) {
        int[] degree = new int[n];
        
        // 统计每个城市的度数
        foreach (var road in roads) {
            degree[road[0]]++;
            degree[road[1]]++;
        }
        
        // 创建城市索引数组并按度数排序
        int[] cities = new int[n];
        for (int i = 0; i < n; i++) {
            cities[i] = i;
        }
        Array.Sort(cities, (a, b) => degree[a].CompareTo(degree[b]));
        
        // 分配值
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            value[cities[i]] = i + 1;
        }
        
        // 计算总重要性
        long result = 0;
        foreach (var road in roads) {
            result += value[road[0]] + value[road[1]];
        }
        
        return result;
    }
}

var maximumImportance = function(n, roads) {
    // 统计每个城市的度数
    const degree = new Array(n).fill(0);
    for (const [a, b] of roads) {
        degree[a]++;
        degree[b]++;
    }
    
    // 按度数排序城市索引
    const cities = Array.from({length: n}, (_, i) => i);
    cities.sort((a, b) => degree[a] - degree[b]);
    
    // 分配值
    const value = new Array(n);
    for (let i = 0; i < n; i++) {
        value[cities[i]] = i + 1;
    }
    
    // 计算总重要性
    let result = 0;
    for (const [a, b] of roads) {
        result += value[a] + value[b];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + m)其中 n 是城市数量，m 是道路数量。排序需要 O(n log n)，统计度数和计算结果需要 O(m)
空间复杂度O(n)需要存储度数数组、城市索引数组和值数组