并查集 – D – Recommendations

#include<bits/stdc++.h> 
#define N 200005
#define endl '\n' 
#define _for(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long ll;  
struct Node{
    int num; ll t;
    bool operator < (const Node &o){ 
        return t>o.t;
    }
}a[N];
map<int,int > F;
int find(int k){
    if(F[k]==0){
        return k;
    }
    else return F[k]=find(F[k]); 
}
void link(int a,int b){
    int fa=find(a),fb=find(b);
    if(fa!=fb) F[fa]=fb;
}
ll res;
int main(){    
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);     
    int n ; cin>>n;
    _for(i,1,n+1) cin>>a[i].num;
    _for(i,1,n+1) cin>>a[i].t;
    sort(a+1,a+n+1);
    _for(i,1,n+1){
        int tem=a[i].num;
        int to= find(tem);
        link(to,to+1);
        if( to == tem ) ;
        else { 
            res+= 1ll*(to-tem)*a[i].t;
        }
    }
    cout<<res<<endl;
    return 0;
}