烦人の建交：贪心

正解

贪心策略就是对于同一个亲戚，我们只需要选择时间最少的即可。在处理每个亲戚的时间时，我们可以用 vis 数组记录是否见到过。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int u,dis;
}a[10000005];
bool vis[10000005];
bool cmp(node a,node b){return a.dis < b.dis;}
int main(){
    int n; cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i].u >> a[i].dis;
    sort(a + 1,a + n + 1,cmp);
    long long ans = 0;
    for(int i = 1;i <= n;i++){
    	if(vis[a[i].u] == 0){
        	vis[a[i].u] = 1;
            ans += a[i].dis;
        }
    }
    cout << ans;
    return 0;
}

时间复杂度：$O(N \log N)$
预计得分：$120pts$