题目名称	1450. [USACO Mar]提高速度
输入输出	`sboost.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cqw 于2013-11-30加入
开放分组	全部用户
提交状态
分类标签	贪心数学
	分享题解

通过：19，提交：58，通过率：32.76%
请叫我“读者”	100	0.008 s	0.28 MiB	C++
devil	100	0.008 s	0.46 MiB	C++
cstdio	100	0.009 s	0.46 MiB	C++
sqyon	100	0.009 s	0.51 MiB	C++
超级傲娇的AC酱	100	0.010 s	0.28 MiB	C++
毕之	100	0.010 s	0.39 MiB	Pascal
FoolMike	100	0.011 s	0.42 MiB	C++
digital-T	100	0.012 s	0.58 MiB	C++
HouJikan	100	0.013 s	0.43 MiB	C++
请叫我“读者”	100	0.014 s	0.28 MiB	C++

本题关联比赛
20131130
20131130

关于提高速度的近10条评论(全部评论)
回复 @张灵犀不和我��般见识真可怕呢（笑 : 0 2015-10-13 17:23 8楼
（bgm45）张灵犀不和我一般见识真可怕呢（笑 2015-09-20 16:31 7楼
脑子无限秀逗 HouJikan 2014-09-28 21:44 6楼
回复 @cstdio : 没理领会你什么意思。f/m无法确定一定值来计算吧。如果不依序逐次更新f/m的值的话，会出现以下情况：Ａ＋Ｂ＋Ｃ配件（有序）使得Ｆ／Ｍ最大，而Ｄ虽大于ｆ／ｍ（ｃｏｓｎｔ），但是却比最优值低。超级傲娇的AC酱 2013-11-30 20:23 5楼
回复 @CH.Genius_King : 没弄明白……能举个例子吗？ cstdio 2013-11-30 20:23 4楼
因为$a=\frac{ \sum_{i=1}^{n} {Fi}}{ \sum_{i=1}^{n} {Mi}}$ 可知，任意可使加速度增大的配件应满足 $\frac{F[i]}{M[i]}> \frac{F}{M}$ 否则会对整体产生阻碍作用。因此F[i]/M[i]越大，越优。得到配件按加速度降序的序列，从最大值开始扫描，若满足上述关系，则加入一次优配件仍可使汽车加速[由于汽车本身F/M决定]，可以发现，每加一次 $\frac{F}{M}$都会增加（前提是满足上式，可以用等比性质证明）。直到不满足为止。超级傲娇的AC酱 2013-11-30 19:59 3楼
回复 @CH.Genius_King : ①用一个f/m值更大的配件代替某个配件显然更优，因此选取的是f/m值前若干大的配件 ②加入前若干大配件导致的a值变化显然是单峰的，因此O(n)扫描 cstdio 2013-11-30 19:32 2楼
直接上贪心，竟然对了求大神给证明 Chenyao2333 2013-11-30 18:32 1楼

1450. [USACO Mar]提高速度

★☆ 输入文件：sboost.in 输出文件：sboost.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

Bessie在为即将来临的汽车大赛准备赛车，它想购买一些附加装备来增强赛车的性能。赛车当前的质量为M(1≤M≤1，000)，具有F (1≤F≤1,000，000)大小的动力。商店里有N(1≤N≤10，000)个装备，编号1…N。Bessie可以随便购买多少个装备，但每个装备只能买一件。

装备P_i可以增加F_i (1≤F_i≤1,000，000)的动力，但同时也增加了M_i(1≤M_i≤1,000)的质量。牛顿第二定律说：F=MA，F是力，M是质量，A是加速度。如果Bessie希望赛车的加速度最大(否则的话希望赛车的质量最轻)，那么它应当购买多少附加装备呢?

例如，一辆赛车的初始值为F=1500，M=100，有4种附加装备：

i F_i M_i

1 250 25

2 150 9

3 120 5

4 200 8

如果只购买装备2，加速度为：(1500+150)/(100+9)=165/109=15.13761。

下表列出了购买装备的各种组合情况，在第1列中，1表示要买，0表示不买。

Parts Aggregate Aggregate

1234 F M F/M

0000 1500 100 15.0000

0001 1700 108 15.7407

0010 1620 105 15.4286

001 1 1820 113 16.1062

0100 1650 109 15.1376

0101 1850 117 15.8120

0110 1770 114 15.5263

011 1 1970 122 16.1475<-最大的F/M

1000 1750 125 14.0000

1001 1950 133 14.6617

1010 1870 130 14.3846

1011 2070 138 15.0000

1100 1900 134 14.179l

1101 2100 142 14.7887

1110 2020 139 14.5324

1111 2220 147 15.1020

因此，最佳的购买方案是2，3，4。

【输入格式】

第1行：3个整数F，M，N

第2…N+I行：第i+l行包含2个整数F_i和M_i

【输出格式】

若干行，每行输出一个要购买的装备的编号，以升序输出。如果不需要购买，则输出'NONE'(不要引号)。

数据保证答案唯一。

【样例输入】

【样例输出】

2
3
4

【提示】

在此键入。

【来源】

在此键入。