青少年编程知识记录 codecoming

【题解】最短距离

【题目描述】

在一条一维的直线上,存在着 n 台显示器和 n 个电源插座。老师给小蓝布置了个任务:负责将每台显示器通过电源线与一个插座相连接(每个插座最多只能给一台显示器供电);同时,老师希望所消耗的电源线的长度尽可能的少,请你帮小蓝计算下电源线的最小消耗长度为多少?

为了便于计算,你只需要考虑直线距离即可。

【输入描述】

输入的第一行包含一个正整数 n。

接下来 n 行,每行包含一个整数 xi,依次表示每台显示器的坐标。

接下来 n 行,每行包含一个整数 yi,依次表示每个插座的坐标。

【输出描述】

输出一行包含一个整数表示答案。

【样例输入】

2  0  1  2  3

【样例输出】

4

【数据约定】

对于20%的数据,1<=n<=10,  0<=Xi,Yi<=100

对于40%的数据,1<=n<=100, 0<=Xi,Yi<=10^3

对于60%的数据,1<=n<=1000, 0<=Xi,Yi<=10^5

对于80%的数据,1<=n<=10000,0<=Xi,Yi<=10^9

对于所有数据,1<=n<=50000,0<=Xi,Yi<=10^9



【题目分析】

相似题目:使每位同学都有座位的最少移动次数

贪心。

本题的核心问题是要将n台显示器和n个电源插座进行一一连接,且每个插座最多只能给一台显示器供电,目标是让连接所有显示器和插座所使用的电源线总长度最小。由于是在一维直线上,只需考虑直线距离,也就是两点坐标差值的绝对值。

要实现电源线总长度最小,关键在于将显示器和插座按照坐标从小到大排序,然后依次对应连接,这样就能保证每一对显示器和插座之间的距离之和最小。

【参考答案】

#include<bits/stdc++.h>   using namespace std;  int x[50010],y[50010];  long long sum=0;  int main(){      int n;      cin>>n;      for(int i=1;i<=n;i++){          cin>>x[i];      }      for(int i=1;i<=n;i++){          cin>>y[i];      }      sort(x+1,x+1+n);      sort(y+1,y+1+n);          for(int i=1;i<=n;i++){          sum+=abs(y[i]-x[i]);      }      cout<<sum;      return 0;  }