上海市计算机学会竞赛平台2023年9月月赛丙组点对之和（一）

题目描述

给定两个数列 𝑎1,𝑎2,…,𝑎𝑛a1​,a2​,…,an​ 与 𝑏1,𝑏2,…,𝑏𝑛b1​,b2​,…,bn​，保证这些数字是 11 到 𝑛n 之间的整数，请计算

∑1≤𝑖,𝑗≤𝑛max⁡(𝑎𝑖,𝑏𝑗)1≤i,j≤n∑​max(ai​,bj​)

输入格式

• 第一行：单个整数表示 𝑛n
• 第二行：𝑛n 个整数表示 𝑎1,𝑎2,…,𝑎𝑛a1​,a2​,…,an​
• 第三行：𝑛n 个整数表示𝑏1,𝑏2,…,𝑏𝑛b1​,b2​,…,bn​

输出格式

• 单个整数表示答案

数据范围

• 50%50% 的数据，1≤𝑛≤10,0001≤n≤10,000
• 100%100% 的数据，1≤𝑛≤500,0001≤n≤500,000
• 1≤𝑎𝑖,𝑏𝑗≤1061≤ai​,bj​≤106

样例数据

输入:

5
1 3 9 7 5
10 4 2 8 6

输出:

180

详见代码:

#include <bits/stdc++.h>
using namespace std;
int n;
long long a[500005];
long long b[500005];
long long sum=0;
int main() 
{cin>>n;for (int i=1;i<=n;i++){cin>>a[i];}for (int i=1;i<=n;i++){cin>>b[i];}sort(a+1,a+1+n);sort(b+1,b+1+n);int bp=1;for (int i=1;i<=n;i++){while (a[i]>=b[bp]&&bp<=n){bp++;}sum+=a[i]*(bp-1);}int ap=1;for (int i=1;i<=n;i++){while(b[i]>a[ap]&&ap<=n){ap++;}sum+=b[i]*(ap-1);}cout<<sum;return 0;
}