推 sustainer123: 大師 06/28 13:48
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;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719553401.A.DC8.html