本文主要是介绍上海计算机学会2024年5月月赛丙组距离之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
设 (𝑥,𝑦)(x,y) 与 (𝑥′,𝑦′)(x′,y′) 是平面上的两个点的坐标，它们之间的城市距离定义为
∣𝑥−𝑥′∣+∣𝑦−𝑦′∣∣x−x′∣+∣y−y′∣
给定 𝑛n 个点，请计算所有点对之间的城市距离之和。
输入格式
- 第一行：单个整数 𝑛n。
- 第二行到第 𝑛+1n+1 行：第 𝑖+1i+1 行有两个整数 𝑥𝑖xi 和 𝑦𝑖yi，表示一个点的坐标。
输出格式
- 单个整数：表示所有点对的城市距离之和。
数据范围
- 30%30% 的数据，1≤𝑛≤10001≤n≤1000
- 60%60% 的数据，1≤𝑛≤500001≤n≤50000
- 100%100% 的数据，1≤𝑛≤300,0001≤n≤300,000
- −106≤𝑥𝑖,𝑦𝑖≤106−106≤xi,yi≤106
样例数据
输入:
3
1 1
2 3
1 4
输出:
8
说明:
3 + 3 + 2 = 8
详见代码:
#include <bits/stdc++.h>
using namespace std;
int n;
long long x[300005];
long long y[300005];
long long qx[300005];
long long qy[300005];
long long ans;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>x[i]>>y[i];}sort(x+1,x+n+1);sort(y+1,y+n+1);for(int i=1;i<=n;i++){qx[i]=qx[i-1]+x[i];qy[i]=qy[i-1]+y[i];}for(int i=1;i<=n;i++){ans+=x[i]*(i-1)-qx[i-1];ans+=y[i]*(i-1)-qy[i-1];}cout<<ans;return 0;
}这篇关于上海计算机学会2024年5月月赛丙组距离之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
