此文章可以使用目录功能哟↑(点击上方[+])
比赛链接→Educational Codeforces Round 16
Codeforces Problem 710B Optimal Point on a Line
Accept: 0 Submit: 0
Time Limit: 1 second Memory Limit : 256 megabytes
Problem Description
You are given n points on a line with their coordinates xi. Find the point x so the sum of distances to the given points is minimal.
Input
The first line contains integer n (1?≤?n?≤?3·10^5) — the number of points on the line.
The second line contains n integers xi (?-?10^9?≤?xi?≤?10^9) — the coordinates of the given n points.
Output
Print the only integer x — the position of the optimal point on the line. If there are several optimal points print the position of the leftmost one. It is guaranteed that the answer is always the integer.
Sample Input
1 2 3 4
Sample Output
Hint
Problem Idea
解题思路:
【题意】
一维坐标轴上有n个点
求坐标轴上一点使它到这n个点的距离之和最小,输出这个点的坐标
【类型】
排序求中位数
【分析】
毋庸置疑,为了方便计算,可将n个点的坐标从小到大排序
接着,我们来分析一下,这个点该如何取?
这个点的取法无非两种:
①该点为n个点中的其中一个点
②该点不在这n个点当中,也就是另外取的一点
我们一一分析一下
首先是情况①,我们不妨假设这n个点为x1,x2,……,xk,……,xn(已排好序)
假设我们取了点
若我们取了点
⑵-⑴,得
显然
所以,对于情况①而言,选取n个点中最中间那个点可以使得距离之和最小,即n个数的中位数
我们再来考虑情况②,该点并非这n个点中的一点
我们不妨设该点为x,它介于某两个点(暂时假定这两个点为
我们先求得点x的最小距离之和⑶
⑵-⑶,得
⑶-⑴,得
要使得取点x时距离之和最小,需满足
显然是无解的
综上所述,此题就是求解n个数的中位数
【时间复杂度&&优化】
O(nlogn)
题目链接→Codeforces Problem 710B Optimal Point on a Line
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 300005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
int s[N];
int main()
{int n,i;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&s[i]);sort(s+1,s+1+n);printf("%d\n",s[(n+1)/2]);return 0;
}