P1842 奶牛玩杂技

    • 128通过
    • 359提交
  • 题目提供者 JOHNKRAM 管理员
  • 评测方式 云端评测
  • 标签 USACO
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Farmer John 养了N(1<=N<=50,000)头牛,她们已经按1~N依次编上了号。FJ所不知道的是,他的所有牛都梦想着从农场逃走,去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳(她们还尝试过把自己装在大炮里发射出去,但可想而知,结果是悲惨的) 。最终,她们决定练习一种最简单的杂技:把所有牛都摞在一起, 比如说, 第一头牛站在第二头的身上, 同时第二头牛又站在第三头牛的身上...最底下的是第 N头牛。

    题目描述

    每头牛都有自己的体重以及力量,编号为 i 的奶牛的体重为

    W_i(1<=W_i<=10,000),力量为 S_i(1<=S_i<=1,000,000,000)。

    当某头牛身上站着另一些牛时它就会在一定程度上被压扁,我们不妨把它被压扁的程度叫做它的压扁指数。对于任意的牛,她的压扁指数等于摞在她上面的所有奶牛的总重(当然不包括她自己)减去它的力量。奶牛们按照一定的顺序摞在一起后, 她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。

    你的任务就是帮助奶牛们找出一个摞在一起的顺序,使得总压扁指数最小。

    输入输出格式

    输入格式:

    第一行:N

    接下来N行,每行两个数:Wi和Si

    输出格式:

    最小总压扁指数

    输入输出样例

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