题目名称 2928. [USACO Open18] Talent Show
输入输出 talent.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2018-04-11
开放分组 全部用户
提交状态
分类标签
通过:0, 提交:0, 通过率:0%
关于 Talent Show 的讨论
冒泡
GravatarHtBest
2018-04-13 07:07 1楼

2928. [USACO Open18] Talent Show

★★   输入文件:talent.in   输出文件:talent.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

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

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

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

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

【输入格式】

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

【输出格式】

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

【输入样例】

3 15
20 21
10 11
30 31

【输出样例】

1066

【提示】

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

【来源】

USACO Open18 Gold

供题:Brian Dean