题目描述

在一条大路一旁有许多栋楼，每栋楼里有许多小学生（哈哈哈一波小学生来袭！）。但是这条路上没有小学！！！！所以唯恐世界不乱的牛A打算在路上（汽车什么的都不敢来这个小学生云集的地方咯，所以不用担心安全问题）任选一点（可以和楼重合，当然也可以不重合）建立一个小学，且使所有小学生上学走的路程之和最短。

输入格式：

第1行一个整数n（1 <= n <= 10000），表示路两旁楼的数量。

接下来的n行，每行2个整数ai（0 <= ai <= 20000）和bi（1<= bi <= 10），分别表示楼的横坐标（真的很巧，所有楼都在同一条直线上，即纵坐标都相等）和楼里小学生的人数。

数据保证ai互不相同。

输出格式：

所有小学生走的最小的路程之和。

友情提示

所有数据的n均大于1000

题解

带权中位数，很明显了吧？还是一维的

顺手就码出来了，c++自带快排好评，终于摆脱了苦逼的fp(大概？)

代码

#include 
     
      #include 
      
       #include 
       
        using namespace std;struct pos{    int a,b;};pos x[10001];int n;bool cmp(pos x,pos y){    return x.a>y.a;}int main(){    int sum=0;    scanf("%d",&n);    for (int i=1;i<=n;i++)    {        scanf("%d%d",&x[i].a,&x[i].b);        sum+=x[i].b;    }    sort(x+1,x+n+1,cmp);    int f,t=0,ans=0;    for (int i=1;i<=n;i++)    {        t+=x[i].b;        if (t>sum/2)        {            f=x[i].a;            break;        }    }       for (int i=1;i<=n;i++)        ans+=x[i].b*abs(f-x[i].a);    printf("%d\n",ans);    return 0;}