in degree là gì thế thím, thấy tụi nó cũng hay đặt biến như vIn-degree. Nhạt như nước ốc ao bèo
JavaScript:function maximumImportance(n: number, roads: number[][]): number { const arr = new Array(n).fill(0); for (const [from, to] of roads) { arr[from]++; arr[to]++; } arr.sort((a,b) => a - b); let val = 1, res = 0; for (const item of arr) { res+= val * item; val++ } return res; };
ví dụ với đỉnh A:
lúc đọc xong đề cũng nghĩ ngay đến đồ thị giống fen :V
public class Solution {
public long MaximumImportance(int n, int[][] roads) {
int rank = n;
long[] kvp = new long[n];
for (int i = 0; i < roads.Length; i++)
{
kvp[roads[i][0]]++;
kvp[roads[i][1]]++;
}
long sum = 0;
Array.Sort(kvp, (x, y) => y.CompareTo(x));
for (int i = 0; i < kvp.Length; i++)
{
sum += kvp[i] * rank;
rank--;
}
return sum;
}
}
impl Solution {
pub fn maximum_importance(n: i32, roads: Vec<Vec<i32>>) -> i64 {
let mut n = n as usize;
let mut cities = vec![0; n];
for r in roads {
cities[r[0] as usize] -= 1;
cities[r[1] as usize] -= 1;
}
cities.sort_unstable();
let mut m = 0i64;
for c in cities {
if c == 0 {
break;
}
m -= c as i64 * n as i64;
n -= 1;
}
return m;
}
}
class Solution {
public long maximumImportance(int n, int[][] roads) {
int[] cityConnections = new int[n];
long sumOfImportance = 0;
for(int[] road:roads){
cityConnections[road[0]]++;
cityConnections[road[1]]++;
}
Arrays.sort(cityConnections);
for(int i =0 ;i<n;i++){
sumOfImportance += 1L * cityConnections[i]* (i+1) ;
}
return sumOfImportance;
}
}
class Solution:
def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
indegree = [0]*n
for road in roads:
indegree[road[0]] += 1
indegree[road[1]] += 1
indegree = sorted(indegree, reverse = True)
maxPoint = n
ans = 0
for d in indegree:
ans += maxPoint*d
maxPoint -= 1
return ans
class Solution {
func maximumImportance(_ n: Int, _ roads: [[Int]]) -> Int {
var dictCount:[Int: Int] = [:]
for road in roads {
dictCount[road[0], default: 0] += 1
dictCount[road[1], default: 0] += 1
}
let arrayCount = dictCount.values.sorted(by:>)
var result = 0
for (index, count) in arrayCount.enumerated() {
result += (n - index) * count
}
return result
}
}Tuần này contest ra graph rồi, lâu ko làm graph nhìn lúc mới ra greedy28/06/2024: Bài này là graph giả cầy thôi ae,
Python:return sum((n - i)*c for i, c in enumerate(sorted(Counter(x for road in roads for x in road).values(), reverse = True)))
fake vl
mới thấy hashset chứ chưa nhìn ra graph chỗ nào
cứ làm hash đi, làm ko ra sẽ tự ngộ ra graph thuimới thấy hashset chứ chưa nhìn ra graph chỗ nào
Bài này nhìn có vẻ là union find hơn chứ nhỉ
Union xong làm thế nào bác filter được recipe nào là possible, find lên trên thì không khả thi, find xuống dưới thì root không cố định rồi
5s đầu là mình cũng suy nghĩ dùng Union Find để tính rank đấy. May rút kịp nhận ra là bài này Graph China
Mang ngay đề contest chính thức đến đây. Mang ngay graph của leetcode đến đây. Anh em 2Q Gang và thí sinh tự do của chúng tôi đã sẵn sàng hết rồi. Mang ngay những câu khó nhất đến đây, khó hơn codeforce cho chúng tôi. Tổ chức thi luôn đi. Anh em đâu, xung phongTuần này contest ra graph rồi, lâu ko làm graph nhìn lúc mới ra greedy
via theNEXTvoz for iPhone
Đúng sv trường top có khác, chiến quáMang ngay đề contest chính thức đến đây. Mang ngay graph của leetcode đến đây. Anh em 2Q Gang và thí sinh tự do của chúng tôi đã sẵn sàng hết rồi. Mang ngay những câu khó nhất đến đây, khó hơn codeforce cho chúng tôi. Tổ chức thi luôn đi. Anh em đâu, xung phong
class Solution {
public long maximumImportance(int n, int[][] roads) {
long[] count = new long[n];
long maxSum = 0;
for(int[] road:roads){
count[road[0]]++;
count[road[1]]++;
}
Arrays.sort(count);
for(int i = count.length -1; i>=0;i--){
maxSum += count[i]*n;
n--;
}
return maxSum;
}
}
