2024-06-28 2285. Maximum Total Importance of Roads
You are given an integer n denoting the number of cities in a country. The
cities are numbered from 0 to n - 1.
You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes
that there exists a bidirectional road connecting cities ai and bi.
You need to assign each city with an integer value from 1 to n, where each
value can only be used once. The importance of a road is then defined as the
sum of the values of the two cities it connects.
Return the maximum total importance of all roads possible after assigning the
values optimally.
每个 node 给一个值
edge 权重等于相连两个 node 值的和
目标求 node 让 edge 权重总和最大
edge 权重是由相连的两个 node 决定
为了让 edge 总和最大
连比较多 edge 的 node 应该要给比较大的值
而由于目标是要算 edge 总和
(node_{1,1} + node_{1,2}) + (node_{2,1} + node_{2,2}) +...
可以整理成计算
(node 值 * node 连接的 edge 数)
同时题目不要求回答各 node 值
不用实际一对一对应 node 给值
long long maximumImportance(int n, vector<vector<int>>& roads) {
vector<int> deg(n, 0);
for (int i = 0; i < roads.size(); ++i) {
deg[roads[i][0]]++;
deg[roads[i][1]]++;
}
// 连接 edge 越多的 node 应该要给越大的值
// 只要算总和 排序就好了 不用追踪 index 也不用保留顺序
sort(deg.begin(), deg.end());
long long ans = 0;
for (int i = 0; i < n; ++i) {
// int 可能会溢位
// 另外 C++ index 会差 1
ans += (long long)deg[i] * (i + 1);
}
return ans;
}