P3080 [USACO13MAR]牛跑The Cow Run

    • 164通过
    • 347提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2013
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Farmer John has forgotten to repair a hole in the fence on his farm, and his N cows (1 <= N <= 1,000) have escaped and gone on a rampage! Each minute a cow is outside the fence, she causes one dollar worth of damage. FJ must visit each cow to install a halter that will calm the cow and stop the damage.

    Fortunately, the cows are positioned at distinct locations along a straight line on a road outside the farm. FJ knows the location P_i of each cow i (-500,000 <= P_i <= 500,000, P_i != 0) relative to the gate (position 0) where FJ starts.

    FJ moves at one unit of distance per minute and can install a halter instantly. Please determine the order that FJ should visit the cows so he can minimize the total cost of the damage; you should compute the minimum total damage cost in this case.

    农夫约翰的牧场围栏上出现了一个洞,有N(1 <= N <= 1,000)只牛从这个洞逃出了牧场。这些出逃的奶牛很狂躁,他们在外面到处搞破坏,每分钟每头牛都会给约翰带来1美元的损失。约翰必须用缰绳套住所有的牛,以停止他们搞破坏。

    幸运的是,奶牛们都在牧场外一条笔直的公路上,牧场的大门恰好位于公里的0点处。约翰知道每头牛距离牧场大门的距离P_i(-500,000 <= P_i <= 500,000, P_i != 0)

    约翰从农场大门出发,每分钟移动一个单位距离,每到一头牛所在的地点,约翰就会给它套上缰绳,套缰绳不花时间。按怎样的顺序去给牛套缰绳才能使约翰损失的费用最少?

    输入输出格式

    输入格式:

    * Line 1: The number of cows, N.

    * Lines 2..N+1: Line i+1 contains the integer P_i.

    输出格式:

    * Line 1: The minimum total cost of the damage.

    输入输出样例

    输入样例#1: 复制
    4 
    -2 
    -12 
    3 
    7 
    
    输出样例#1: 复制
    50 
    

    说明

    Four cows placed in positions: -2, -12, 3, and 7.

    The optimal visit order is -2, 3, 7, -12. FJ arrives at position -2 in 2 minutes for a total of 2 dollars in damage for that cow.

    He then travels to position 3 (distance: 5) where the cumulative damage is 2 + 5 = 7 dollars for that cow.

    He spends 4 more minutes to get to 7 at a cost of 7 + 4 = 11 dollars for that cow.

    Finally, he spends 19 minutes to go to -12 with a cost of 11 + 19 = 30 dollars.

    The total damage is 2 + 7 + 11 + 30 = 50 dollars.

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