Dare2Solve
The problem involves assigning values to cities such that the total importance of all roads is maximized. The importance of a road is the sum of the values of the cities it connects. To maximize the total importance, we should assign the highest values to the cities that appear most frequently in the roads array. This is because the importance of each road increases with the values of the cities it connects.
var freq = new Uint32Array(n);
var cnt = new Uint32Array(n);
var res = 0;
var cur = 1;
freq
is an array initialized with zeros, used to count the number of roads connected to each city.cnt
is an array initialized with zeros, used to count the number of cities with each frequency.res
is a variable to store the result (the maximum total importance).cur
is a variable to keep track of the current value being assigned to a city.roads.forEach(([a, b]) => {
++freq[a], ++freq[b]
});
roads
array.[a, b]
, increment the frequency of city a
and city b
by 1.freq.forEach((x) => ++cnt[x]);
freq
array.x
in freq
, increment the count of cities with frequency x
in the cnt
array.cnt.forEach((x, idx) => {
while (x--)
res += idx * cur++
});
cnt
array.x
at index idx
, assign the current value cur
to x
cities, where each assignment increases cur
by 1.idx
(the frequency) and cur
to res
for each assignment.return res;
res
which represents the maximum total importance of all roads after assigning the values optimally.class Solution {
public:
long long maximumImportance(int n, vector<vector<int>>& roads) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<int> freq(n, 0);
vector<int> cnt(n, 0);
long long res = 0;
long long cur = 1;
for (const auto& road : roads) {
++freq[road[0]];
++freq[road[1]];
}
for (const auto& x : freq) {
++cnt[x];
}
for (long long idx = 0; idx < cnt.size(); ++idx) {
for (int i = cnt[idx]; i > 0; --i) {
res += idx * cur++;
}
}
return res;
}
};
class Solution:
def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
freq = [0] * n
cnt = [0] * n
res = 0
cur = 1
for road in roads:
freq[road[0]] += 1
freq[road[1]] += 1
for x in freq:
cnt[x] += 1
for idx in range(len(cnt)):
for _ in range(cnt[idx], 0, -1):
res += idx * cur
cur += 1
return res
class Solution {
public long maximumImportance(int n, int[][] roads) {
int[] freq = new int[n];
int[] cnt = new int[n];
long res = 0;
long cur = 1;
for (int[] road : roads) {
freq[road[0]]++;
freq[road[1]]++;
}
for (int x : freq) {
cnt[x]++;
}
for (int idx = 0; idx < cnt.length; ++idx) {
for (int i = cnt[idx]; i > 0; --i) {
res += idx * cur++;
}
}
return res;
}
}
/**
* @param {number} n
* @param {number[][]} roads
* @return {number}
*/
var maximumImportance = function (n, roads) {
var freq = new Uint32Array(n);
var cnt = new Uint32Array(n);
var res = 0;
var cur = 1;
roads.forEach(([a, b]) => { ++freq[a], ++freq[b] });
freq.forEach((x) => ++cnt[x]);
cnt.forEach((x, idx) => { while(x--) res += idx * cur++ });
return res;
};