涞坊路是一条长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.最小的点一定是建在某个房子上。,
2.这个房子是重点!
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #define lli long long int
8 using namespace std;
9 const int MAXN=100001;
10 void read(lli &n)
11 {
12 char c='+';lli x=0;bool flag=0;
13 while(c<'0'||c>'9')
14 {c=getchar();if(c=='-')flag=1;}
15 while(c>='0'&&c<='9')
16 {x=x*10+(c-48);c=getchar();}
17 flag==1?n=-x:n=x;
18 }
19 lli l,n;
20 struct node
21 {
22 lli x,pep;
23 }a[MAXN];
24 lli tot;
25 lli comp(const node &a,const node &b)
26 {
27 return a.x<b.x;
28 }
29 int main()
30 {
31 read(l);read(n);
32 for(lli i=1;i<=n;i++)
33 {
34 read(a[i].x);read(a[i].pep);
35 tot+=a[i].pep;
36 }
37 tot=(tot+1)/2;
38
39 sort(a+1,a+n+1,comp);
40
41 lli now=0;
42 lli mid=0;
43 for(lli i=1;i<=n;i++)
44 {
45 now+=a[i].pep;
46 if(now>=tot)
47 {
48 mid=i;
49 break;
50 }
51 }
52 lli ans=0;
53 for(lli i=1;i<=n;i++)
54 {
55 ans+=(a[i].pep*abs(a[mid].x-a[i].x));
56 }
57 printf("%lld",ans);
58 return 0;
59 }