点对之和（一）

                                                内存限制: 256 Mb时间限制: 1000 ms

题目描述

给定两个数列 a1,a2,…,ana1​,a2​,…,an​ 与 b1,b2,…,bnb1​,b2​,…,bn​，保证这些数字是 11 到 nn 之间的整数，请计算

∑1≤i,j≤nmax⁡(ai,bj)1≤i,j≤n∑​max(ai​,bj​)

输入格式

• 第一行：单个整数表示 nn
• 第二行：nn 个整数表示 a1,a2,…,ana1​,a2​,…,an​
• 第三行：nn 个整数表示b1,b2,…,bnb1​,b2​,…,bn​

输出格式

• 单个整数表示答案

数据范围

• 50%50% 的数据，1≤n≤10,0001≤n≤10,000
• 100%100% 的数据，1≤n≤500,0001≤n≤500,000
• 1≤ai,bj≤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;
}