上海计算机学会2024年5月月赛C++丙组T4距离之和
发布时间
阅读量：
阅读量
距离之和
内存限制: 256 Mb时间限制: 1000 ms
题目描述
设 (x,y) 与 (x′,y′) 是平面上的两个点的坐标，它们之间的城市距离定义为
∣x−x′∣+∣y−y′∣
给定 n 个点，请计算任意两点的城市距离之和。
输入格式
- 第一行：单个整数 n。
- 第二行到第 n+1 行：第 i+1 行有两个整数 xi 和 yi，表示一个点的坐标。
输出格式
- 单个整数：表示所有点对的城市距离之和。
数据范围
- 30% 的数据，1≤n≤1000
- 60% 的数据，1≤n≤50000
- 100% 的数据，1≤n≤300,000
- −106≤xi,yi≤106
样例数据
输入:
3
1 1
2 3
1 4
输出:
8
说明:
3 + 3 + 2 = 8
解析：x和y可以分开算，都从小到大排序，当前数跟它前边所有数的距离可以用前缀和算出来。
详见代码：
#include <bits/stdc++.h>
using namespace std;
int n;
long long x[300005];
long long y[300005];
long long qx[300005];//x的前缀和
long long qy[300005];//y的前缀和
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;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~