本文主要是介绍上海市计算机学会竞赛平台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;
}
这篇关于上海市计算机学会竞赛平台2023年9月月赛丙组点对之和(一)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!