CF1909_C. Heavy Intervals题解

CF1909_C. Heavy Intervals题解

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

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

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

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

通俗来讲，就是对于两个有序序列，顺序之积之和大于等于乱序之积之和大于逆序之积之和。

我都知道你们在想什么，下面来到了大家喜闻乐见的Ctrl+C/V环节，AC Code走起！

#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("%lld\n",ans);
????}
????return?0;
}

感谢我这个大好人！没登录的人也可以复制哦！

#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("%lld\n",ans);
    }
    return 0;
}

当然登录了是更快捷的。

时间复杂度O(n*log(n))，完全能过。

代码有亿点长，说点注意事项：

①long long问题。

②lower_bound要用multiset里封装的，不要用单独的函数（这样会退化成O(n)）。