P4377 [USACO18OPEN]Talent Show

    • 502通过
    • 1.1K提交
  • 题目提供者 Cherryblossom
  • 评测方式 云端评测
  • 标签 分数规划 背包 贪心 USACO 2018
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Farmer John要带着他的$N$头奶牛,方便起见编号为$1 \ldots N$,到农业展览会上去,参加每年的达牛秀!他的第$i$头奶牛重量为$w_i$,才艺水平为$t_i$,两者都是整数。 在到达时,Farmer John就被今年达牛秀的新规则吓到了:

    (一)参加比赛的一组奶牛必须总重量至少为$W$(这是为了确保是强大的队伍在比赛,而不仅是强大的某头奶牛),并且

    (二)总才艺值与总重量的比值最大的一组获得胜利。

    FJ注意到他的所有奶牛的总重量不小于$W$,所以他能够派出符合规则(一)的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

    输入输出格式

    输入格式:

    输入的第一行包含$N$($1 \leq N \leq 250$)和$W$($1 \leq W \leq 1000$)。下面$N$行,每行用两个整数$w_i$($1 \leq w_i \leq 10^6$)和$t_i$($1 \leq t_i \leq 10^3$)描述了一头奶牛。

    输出格式:

    请求出Farmer用一组总重量最少为$W$的奶牛最大可能达到的总才艺值与总重量的比值。如果你的答案是$A$,输出$1000A$向下取整的值,以使得输出是整数(当问题中的数不是一个整数的时候,向下取整操作在向下舍入到整数的时候去除所有小数部分)。

    输入输出样例

    输入样例#1: 复制
    3 15
    20 21
    10 11
    30 31
    输出样例#1: 复制
    1066
    

    说明

    在这个例子中,总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为11、重量为10的奶牛,但是由于我们需要至少15单位的重量,最优解最终为使用这头奶牛加上才艺值为21、重量为20的奶牛。这样的话才艺与重量的比值为(11+21)/(10+20) = 32/30 = 1.0666666...,乘以1000向下取整之后得到1066。

    供题:Brian Dean

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