P3819 松江1843路

题目描述

涞坊路是一条长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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习自然语言处理

【概率笔记】条件概率这样学才快啦

比如,一个上学期间整天鬼混的学沫,根本就不好好学习,对于他而言,选择题的四个选项ABCD被他选取的概率就为1/4。而对于大学霸来说,题题都会,那么他选取每一个选...

12830
来自专栏小樱的经验随笔

模拟退火算法从原理到实战【基础篇】

  模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达...

50060
来自专栏新智元

【邓侃】哈佛大学机器翻译开源项目 OpenNMT的工作原理

【新智元导读】 2016年12月20日,哈佛大学自然语言处理研究组,宣布开源了他们研发的机器翻译系统 OpenNMT ,并声称该系统的质量已经达到商用水准。本文...

57350
来自专栏互联网杂技

Google用来处理海量文本去重的simhash算法原理及实现

simhash是Google用来处理海量文本去重的算法。 Google出品,你懂的。 simhash最牛逼的一点就是将一个文档,最后转换成一个64位的字节,暂且...

82480
来自专栏贾志刚-OpenCV学堂

基于积分图的二值图像膨胀算法实现

积分图来源与发展 积分图是Crow在1984年首次提出,是为了在多尺度透视投影中提高渲染速度。随后这种技术被应用到基于NCC的快速匹配、对象检测和SURF变换中...

58280
来自专栏编程

Python数据分析-数据预处理

主题 数据预处理 一、数据清洗 主要是删除原始数据集中无关的数据、重复的数据,平滑噪声数据,筛选掉与挖掘主题无关的数据,处理异常值缺失值等操作 1. 缺失...

78260
来自专栏Duncan's Blog

数据挖掘整理

2.1数据清洗:填写缺失值、光滑噪声数据,识别或删除离群点,并解决不一致性来“清理”数据

19230
来自专栏小樱的经验随笔

【机器学习笔记之一】深入浅出学习K-Means算法

摘要:在数据挖掘中,K-Means算法是一种 cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。 ...

31490
来自专栏AI2ML人工智能to机器学习

决策树会有哪些特性?

决策树(Decision Tree)是机器学习中最常见的算法, 因为决策树的结果简单,容易理解, 因此应用超级广泛, 但是机器学习的专家们在设计决策树的时候会考...

15820
来自专栏PPV课数据科学社区

【大数据问答】SPSS是如何做到发现数据质量问题,例如,如何发现缺失值?

SPSS是如何做到发现数据质量问题,例如,如何发现缺失值? (1)系统缺失值、空白值 每一个变量均有可能出现系统缺失或者空白,当数据量巨大时我们根本无法用眼睛...

48040

扫码关注云+社区

领取腾讯云代金券