玄关求调
查看原帖
玄关求调
625671
Zmk2009楼主2024/9/14 22:15
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define mp make_pair
inline bool isdig(char c){return '0' <=c && c <= '9';}
const int N = 1e4 + 5;
inline ll read(){
    ll x = 0 , f = 1;
    char c = getchar();
    while (!isdig(c)){
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdig(c)){
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x * f;
}
pii a[N];
ll pre[N];
int vis[N];
void init(int n){
    for (int i = 1; i <= n ; i ++){
        vis[i] = 0;
        pre[i] = i - 1;
    }
}
int find(int x){
    if (vis[x]) return pre[x] = find(pre[x]);
    return x;
}
bool cmp(pii a , pii b){
    if (a.fi != b.fi) return a.fi > b.fi;
    else return a.se < b.se;
}
void write(int x){
    if (x < 0){
        x = -x;
        putchar('-'); 
    }
    if (x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}
ll val[N];
int main(){
    // freopen("A.in","r",stdin);
    int n = read();
    for (int i = 1 ; i <= n ; i++){
        a[i].fi = read() , a[i].se = read();
    }
    init(n);
    sort(a + 1, a + n + 1, cmp);
    // for (int i = 1 ; i <= n ;i ++){
    //     // cout << a[i].fi << " " << a[i].se << endl;
    // }
    for (int i = 1 ; i <= n ; i ++){
        int p = find(a[i].se);
        // cout << "s" << p << endl;
        if (p == 0) continue;
        val[p] = a[i].fi;
        vis[p] = 1;
    }
    ll sum = 0;
    for (int i = 1;  i <= 10000 ; i ++) sum += val[i];
    // for (int i = 0 ; i < 10 ; i ++) cout << val[i] << endl;
    write(sum);
    putchar('\n');
    return 0;
}

wa * 2 #7 #8

2024/9/14 22:15
加载中...