P3819 松江1843路
2018-06-17 22:18:43来源:未知 阅读 ()
题目描述
涞坊路是一条长L米的道路,道路上的坐标范围从0到L,路上有N座房子,第i座房子建在坐标为x[i]的地方,其中住了r[i]人。
松江1843路公交车要在这条路上建一个公交站,市政府希望让最多的人得到方便,因此希望所有的每一个的居民,从家到车站的距离的总和最短。
公交站应该建在哪里呢?
输入输出格式
输入格式:
第一行输入L、N。
接下来N行,每行两个整数x[i]和r[i]。
输出格式:
一个整数,最小的每个人从家到车站的距离的总和。
输入输出样例
100 3 20 3 50 2 70 1
110
100 2 0 1 100 10
100
10000000000 5 3282894320 391 4394338332 929 6932893249 181 7823822843 440 9322388365 623
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:动态库和静态库的理解
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash