1096 距离之和最小 基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题 收藏 关注 X轴上有N个点，求X轴上一点使它到这N个点的距离之和最小，输出这个最小的距离之和。 Input 第1行：点的数量N。(2 <= N <= 10000) 第2 - N + 1行：点的位置。（-10^9 <= P[i] <= 10^9) Output 输出最小距离之和 Input示例 5 -1 -3 0 7 9 Output示例 20 思路：首先这题应该是n个点里面选一个。
这题要明白， 首先两点之间线段最短，举个例子， 1 2 3 4 5，5个点， 选3的话， 连接对称点24， 15，就好了， 如果选2的话， 连接13,然后4，5都是单向连过去的。。。画个图就明白了~
所以总结下，从n个点，选1一个点要所有点到他距离和最短， 就选这n个点里中间那个点，如果偶数个，中间那两个随便选， 如果在坐标轴上找一个点， 如果是奇数个数，就选中间哪个， 如果是偶数个，中间两个点之内所有的点都可以，因为每俩个数之间的任意位置到俩点的和都是一样的
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int maxn = 1e4 + 5; ll a[maxn]; int main() { int n; while(~scanf("%d", &n)) { ll ans = 0; for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a+1, a+1+n); for(int i = 1; i <= n; i++) { ans += abs(a[(n+1)/2]-a[i]); } printf("%lld\n", ans); } return 0; } 1108 距离之和最小 V2 基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注 三维空间上有N个点, 求一个点使它到这N个点的曼哈顿距离之和最小，输出这个最小的距离之和。 点(x1,y1,z1)到(x2,y2,z2)的曼哈顿距离就是|x1-x2| + |y1-y2| + |z1-z2|。即3维坐标差的绝对值之和。 Input 第1行：点的数量N。(2 <= N <= 10000) 第2 - N + 1行：每行3个整数，中间用空格分隔，表示点的位置。（-10^9 <= X[i], Y[i], Z[i] <= 10^9) Output 输出最小曼哈顿距离之和。 Input示例 4 1 1 1 -1 -1 -1 2 2 2 -2 -2 -2 Output示例 18 相关问题 距离之和最小 20 距离之和最小 V3 40思路：这一题跟上一题一模一样，只不过这一题是三维的了， 这三维是独立的， 所以化为三个一维的就好了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 1e4 + 5; typedef long long ll; ll x[maxn], y[maxn], z[maxn], n; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%lld%lld%lld", &x[i], &y[i], &z[i]); } sort(x+1, x+1+n); sort(y+1, y+1+n); sort(z+1, z+1+n); ll a = x[(n+1)/2], b = y[(n+1)/2], c = z[(n+1)/2]; long long ans = 0; for(int i = 1; i <= n; i++) { ans += abs(x[i]-a) + abs(y[i]-b) + abs(z[i]-c); } printf("%lld\n", ans); return 0; } 1110 距离之和最小 V3 基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注 X轴上有N个点，每个点除了包括一个位置数据X[i]，还包括一个权值W[i]。该点到其他点的带权距离 = 实际距离 * 权值。求X轴上一点使它到这N个点的带权距离之和最小，输出这个最小的带权距离之和。 Input 第1行：点的数量N。(2 <= N <= 10000) 第2 - N + 1行：每行2个数，中间用空格分隔，分别是点的位置及权值。（-10^5 <= X[i] <= 10^5，1 <= W[i] <= 10^5) Output 输出最小的带权距离之和。 Input示例 5 -1 1 -3 1 0 1 7 1 9 1 Output示例 20 思路：智商压制。。。 每个点的权值是w【i】， 其实可以想象成， 在x【i】上有 w【i】个点， 每个点没有权值， 这么多点，求哪个最近， 肯定还是找中位数。。太奇妙了。。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 1e4 + 5; typedef long long ll; struct node { ll x, w; }a[maxn]; int cmp(node a, node b) { return a.x < b.x; } int main() { ll n, sum = 0, temp = 0, x; scanf("%lld", &n); for(int i = 1; i <= n; i++) { scanf("%lld%lld", &a[i].x, &a[i].w); sum += a[i].w; } sort(a+1, a+1+n, cmp); for(int i = 1; i <= n; i++) { temp += a[i].w; if(temp >= sum/2) { x = a[i].x; break; } } ll ans = 0; for(int i = 1; i <= n; i++) { ans += abs(a[i].x-x)*a[i].w; } printf("%lld\n", ans); return 0; }