P3819 松江1843路

    • 563通过
    • 1.6K提交
  • 题目提供者 lin_toto 対立
  • 评测方式 云端评测
  • 标签 前缀和 数论,数学 模拟
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。