Table of Contents

SGU114 解题手记
　　题目意思是给出数轴上的一些点（有重复的），要求一个点，使得这些点到所求点的距离之和最小。只要求这些点的坐标的中位数就行了。中位数是一个排序好的序列中处在中间位置的一个或两个数。也就是说题目的答案不是唯一的。
　　Submit 1: TLE on 12。怀疑又是iostream出了问题。
　　Submit 2: AC。真无语了，15000*2的数据量，用iostream居然TLE。
　　faster_noi补充：WA on 14。用pascal的注意，题目说数字是用空格分隔的，虽然样例中有换行，但应该以题目要求为准，用Readln读数据会造成WA on 14。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

//AC
#include <cstdio>
#include <cstdlib>
//#include <iomanip>
using namespace std;
 
struct city
{
    float x;
    unsigned long p;
};
 
int compare_x(const void *ta,const void *tb)
{
    city *a=(city*)ta,*b=(city*)tb;
    if (a->x < b->x) return -1;
    else if (a->x == b->x) return 0;
    else return 1;
}
 
int main()
{
    city cities[15000];
    int n,i;
    scanf("%d",&n);
    for (i=0;i<n;++i)
    {
        scanf("%f %u",&cities[i].x,&cities[i].p);
    }
    qsort(cities,n,sizeof(city),compare_x);
    for (i=1;i<n;++i)
    {
        cities[i].p+=cities[i-1].p;
    }
    unsigned long t=cities[n-1].p/2;
    for (i=0;i<n;++i)
        if (cities[i].p>=t) break;
    printf("%1.5f\n",cities[i].x);
    return 0;
}