Codeforces Round \ # 623 D. 권장 사항 및 검색 집합

D. Recommendations time limit per test2 seconds memory limit per test512 megabytes inputstandard input outputstandard output VK news recommendation system daily selects interesting publications of one of n disjoint categories for each user. Each publication belongs to exactly one category. For each category i batch algorithm selects ai publications.
The latest A/B test suggests that users are reading recommended publications more actively if each category has a different number of publications within daily recommendations. The targeted algorithm can find a single interesting publication of i-th category within ti seconds.
What is the minimum total time necessary to add publications to the result of batch algorithm execution, so all categories have a different number of publications? You can’t remove publications recommended by the batch algorithm.
Input The first line of input consists of single integer n — the number of news categories (1≤n≤200000).
The second line of input consists of n integers ai — the number of publications of i-th category selected by the batch algorithm (1≤ai≤109).
The third line of input consists of n integers ti — time it takes for targeted algorithm to find one new publication of category i (1≤ti≤105).
Output Print one integer — the minimal required time for the targeted algorithm to get rid of categories with the same size.
Examples inputCopy 5 3 7 9 7 8 5 2 5 7 5 outputCopy 6 inputCopy 5 1 2 3 4 5 1 1 1 1 1 outputCopy 0 Note In the first example, it is possible to find three publications of the second type, which will take 6 seconds.
In the second example, all news categories contain a different number of publications.
제목: n 권 의 책의 수량 과 한 권 의 책 을 늘 리 는 대 가 를 주 고 n 종의 서로 다른 책의 수량 을 서로 다른 상황 으로 두 고 최소 대가 가 얼마 인지 물 어보 자.
사고: 우선 최소 대가 로 욕심 을 부 리 는 사상 은 대가 가 클 수록 증가 하 는 횟수 가 적어 야 한 다 는 것 이다. 그 다음 에 n 권 책의 수량 이 다 르 는 지 아 닌 지 를 어떻게 판단 하 는 지 여 기 는 다른 것 을 사용 하여 집 을 찾 았 다.

#include 

using namespace std;

const int N = 200005;

#define LL long long
struct node
{
    int num;
    int time;
}a[N];

bool cmp(node a,node b)
{
    if(a.time != b.time)
        return a.time > b.time;

    return a.num > b.num;
}

map<int,int> fa;///    1e9    map  fa  

int findx(int x)
{
    if(fa[x] == 0)///             
        return x;
    return fa[x] = findx(fa[x]);
}

void join(int x,int y)
{
    int xx = findx(x);
    int yy = findx(y);

    if(xx != yy)
        fa[xx] = yy;
}

int main()
{
    int n;

    cin >> n;

    for(int i = 1;i <= n;i ++)
        cin >> a[i].num;

    for(int i = 1;i <= n;i ++)
        cin >> a[i].time;

    sort(a + 1,a + 1 + n,cmp);

    LL res = 0;

    for(int i = 1;i <= n;i ++)
    {
        int father = findx(a[i].num);///      

        if(father != a[i].num)
            res += 1LL*(father - a[i].num)*a[i].time;

        join(father,father + 1);///  +1       
    }

    cout << res << '
';

    return 0;
}