CF1909_C. Heavy Intervals题解_代码007(未授权)

本文介绍: ②lower_bound要用multiset里封装的，不要用单独的函数（这样会退化成O(n)）。我都知道你们在想什么，下面来到了大家喜闻乐见的Ctrl+C/V环节，AC Code走起！通俗来讲，就是对于两个有序序列，顺序之积之和大于等于乱序之积之和大于逆序之积之和。这题已经出的很直了……可能也有暴力做法，大家可以尝逝，我直接将数论方法。时间复杂度O(n*log(n))，完全能过。没登录的人也可以复制哦！题目翻译如下：（图片来源：洛谷）①long long问题。当然登录了是更快捷的。

题目传送门（Problem – C – CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1909/problem/C）。

题目翻译如下：（图片来源：洛谷）

这题已经出的很直了……可能也有暴力做法，大家可以尝逝，我直接将数论方法。

先给亿点前置芝士（排序不等式）：

#include<bits/stdc++.h>
#define N 110000
using namespace std;
multiset<int>tl={};
int a[N]={},c[N]={},l[N]={},r[N]={},n=0,t=0;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        tl.clear();
        for(int i=1;i<=n;i++){
            scanf("%d",&l[i]);
            tl.insert(l[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&r[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&c[i]);
        }
        sort(r+1,r+1+n);
        for(int i=1;i<=n;i++){
            auto id=tl.lower_bound(r[i]);
            id--;
            a[i]=r[i]-(*id);
            tl.erase(id);
        }
        sort(a+1,a+1+n);
        sort(c+1,c+1+n);
        long long ans=0;
        for(int i=1;i<=n;i++){
            ans+=a[i]*1LL*c[n-i+1];
        }
        printf("%lldn",ans);
    }
    return 0;
}