CF1909_C. Heavy Intervals题解
https://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(“%lldn“,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("%lldn",ans);
}
return 0;
}当然登录了是更快捷的。
时间复杂度O(n*log(n))，完全能过。
代码有亿点长，说点注意事项：
①long long问题。
②lower_bound要用multiset里封装的，不要用单独的函数（这样会退化成O(n)）。
原文地址:https://blog.csdn.net/sluckystar/article/details/135384870
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_52950.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
