首页 > 代码库 > P3819 松江1843路
P3819 松江1843路
题目描述
涞坊路是一条长L米的道路，道路上的坐标范围从0到L，路上有N座房子，第i座房子建在坐标为x[i]的地方，其中住了r[i]人。
松江1843路公交车要在这条路上建一个公交站，市政府希望让最多的人得到方便，因此希望所有的每一个的居民，从家到车站的距离的总和最短。
公交站应该建在哪里呢？
输入输出格式
输入格式：
第一行输入L、N。
接下来N行，每行两个整数x[i]和r[i]。
输出格式：
一个整数，最小的每个人从家到车站的距离的总和。
输入输出样例
输入样例#1：
100 320 350 270 1
输出样例#1：
110
输入样例#2：
100 20 1100 10
输出样例#2：
100
输入样例#3：
10000000000 53282894320 3914394338332 9296932893249 1817823822843 4409322388365 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 node21 {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 }
P3819 松江1843路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。