CF797F Mice and Holes

    • 30通过
    • 69提交
  • 题目来源 CodeForces 797F
  • 评测方式 RemoteJudge
  • 标签
  • 难度 省选/NOI-
  • 时空限制 1500ms / 256MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    n个老鼠,m个洞,告诉你他们的一维坐标和m个洞的容量限制,问最小总距离。

    题目描述

    One day Masha came home and noticed $ n $ mice in the corridor of her flat. Of course, she shouted loudly, so scared mice started to run to the holes in the corridor.

    The corridor can be represeted as a numeric axis with $ n $ mice and $ m $ holes on it. $ i $ th mouse is at the coordinate $ x_{i} $ , and $ j $ th hole — at coordinate $ p_{j} $ . $ j $ th hole has enough room for $ c_{j} $ mice, so not more than $ c_{j} $ mice can enter this hole.

    What is the minimum sum of distances that mice have to go through so that they all can hide in the holes? If $ i $ th mouse goes to the hole $ j $ , then its distance is $ |x_{i}-p_{j}| $ .

    Print the minimum sum of distances.

    输入输出格式

    输入格式:

    The first line contains two integer numbers $ n $ , $ m $ ( $ 1<=n,m<=5000 $ ) — the number of mice and the number of holes, respectively.

    The second line contains $ n $ integers $ x_{1},x_{2},...,x_{n} $ ( $ -10^{9}<=x_{i}<=10^{9} $ ), where $ x_{i} $ is the coordinate of $ i $ th mouse.

    Next $ m $ lines contain pairs of integer numbers $ p_{j},c_{j} $ ( $ -10^{9}<=p_{j}<=10^{9},1<=c_{j}<=5000 $ ), where $ p_{j} $ is the coordinate of $ j $ th hole, and $ c_{j} $ is the maximum number of mice that can hide in the hole $ j $ .

    输出格式:

    Print one integer number — the minimum sum of distances. If there is no solution, print -1 instead.

    输入输出样例

    输入样例#1: 复制
    4 5
    6 2 8 9
    3 6
    2 1
    3 6
    4 7
    4 7
    
    输出样例#1: 复制
    11
    
    输入样例#2: 复制
    7 2
    10 20 30 40 50 45 35
    -1000000000 10
    1000000000 1
    
    输出样例#2: 复制
    7000000130
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。