https://www.luogu.org/problem/show?pid=3819
题目描述
涞坊路是一条长L米的道路，道路上的坐标范围从0到L，路上有N座房子，第i座房子建在坐标为x[i]的地方，其中住了r[i]人。
松江1843路公交车要在这条路上建一个公交站，市政府希望让最多的人得到方便，因此希望所有的每一个的居民，从家到车站的距离的总和最短。
公交站应该建在哪里呢？
输入输出格式
输入格式：
第一行输入L、N。
接下来N行，每行两个整数x[i]和r[i]。
输出格式：
一个整数，最小的每个人从家到车站的距离的总和。
输入输出样例
输入样例#1：
100 3
20 3
50 2
70 1
输出样例#1：
110
输入样例#2：
100 2
0 1
100 10
输出样例#2：
100
输入样例#3：
10000000000 5
3282894320 391
4394338332 929
6932893249 181
7823822843 440
9322388365 623
输出样例#3：
5473201404068
说明
样例解释1
当建在坐标40的时候，所有人距离车站的距离总和为 |20−40|×3+|50−40|×2+|70−40|×1=110。
数据范围和约定
对于10%的数据，1≤N≤50，R[i]=1。
对于30%的数据，1≤N≤100，R[i]≤10，1≤L≤1000。
对于70%的数据，1≤N≤1000，R[i]≤100，1≤L≤10^6。
对于全部数据，1≤L≤10^10，1≤N≤10^5，0≤x[i]≤L，1≤r[i]≤1000
首先车站一应会在某个房子处，
将所有的人抽象到数轴上，找到人数的中位数，
然后用排升序的房子找到人数>=中位数的房子，最后统计答案就可以了
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdio> 4 5 #define LL long long 6 7 using namespace std; 8 9 const int N(1e5+15); 10 LL L,n,num,cnt,pos,ans; 11 12 struct Node 13 { 14 LL pos,cnt; 15 }p[N]; 16 bool cmp(Node a,Node b) 17 { 18 return a.pos<b.pos; 19 } 20 21 void read(LL &x) 22 { 23 int ch=getchar();x=0; 24 for(;ch<'0'||ch>'9';) ch=getchar(); 25 for(;ch>='0'&&ch<='9';ch=getchar()) 26 x=ch-'0'+x*10; 27 } 28 29 int main() 30 { 31 read(L); read(n); 32 for(int i=1;i<=n;i++) 33 read(p[i].pos),read(p[i].cnt),num+=p[i].cnt; 34 num>>=1; sort(p+1,p+n+1,cmp); 35 for(LL i=1;i<=n;i++) 36 { 37 cnt+=p[i].cnt; 38 if(cnt>=num) 39 { 40 pos=p[i].pos; 41 break; 42 } 43 } 44 for(int i=1;i<=n;i++) 45 ans+=abs(pos-p[i].pos)*p[i].cnt; 46 printf("%lld",ans); 47 return 0; 48 }