首页 > 代码库 > P3819 松江1843路(洛谷月赛)
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
首先我们知道车站一定会建在所有人的中间,这样距离才可能最小,
这道题先把人数加起来,然后求中位数,相当于把n个人拆成n个点然后求中位数
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstdlib> 4 #include<cmath> 5 #define LL long long 6 using namespace std; 7 8 struct node{ 9 LL pos,num;10 bool operator < (const node &a) const 11 {12 return pos < a.pos;13 }14 }t[100100];15 LL l,n,sum,ans,s,p;16 17 int main()18 {19 scanf("%lld%lld",&l,&n);20 for (LL i=1; i<=n; ++i)21 {22 scanf("%lld%lld",&t[i].pos,&t[i].num);23 sum += t[i].num; 24 }25 sort(t+1,t+n+1);26 sum = (sum+1)/2;27 for (LL i=1; i<=n; ++i)28 {29 s += t[i].num;30 if (s>=sum) 31 {32 p = t[i].pos;33 break;34 }35 }36 for (LL i=1; i<=n; ++i)37 ans += abs(t[i].pos-p)*t[i].num;38 printf("%lld",ans);39 return 0;40 }
P3819 松江1843路(洛谷月赛)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。