P2989 [USACO10MAR] Need For Speed S

题目描述

已知两个整数 $M$ ，$F$，以及 $n$ 对整数 $M_i$ ，$F_i$ ，设$X_i = 1\text{或}0$，求 $\large \frac{F+\sum\limits_{i=1}^{n}X_i \times F_i}{M+\sum\limits_{i=1}^{n}X_i \times M_i}$ 的最大值。

在此基础上最小化 $\sum\limits_{i=1}^{n}X_i \times M_i + M$。

输入格式

第一行三个整数 $F,M,n (n,M \le 10^4,F \le 10^6)$

下来 $n$ 行，每行两个数 $F_i,M_i(M_i \le 10^4,F_i \le 10^6)$

输出格式

输出最终的，按照原始顺序排好序的方案$\{i | X_i = 1\}$ 。

全部 $X_i$ 都为0，则输出 NONE。

输入

1500 100 4 
250 25 
150 9 
120 5 
200 8

输出

2 
3 
4

P2989 [USACO10MAR] Need For Speed S

题目描述

Bessie 正在为即将到来的赛车比赛作准备。

她有一辆赛车，质量为 $M$，且可以提供 $F$ 的力。现在她想要给这辆赛车安装一些零件（总共有 $N$ 个零件），每个零件具有属性 $M_i$ 和 $F_i$，表示其质量以及可以提供的力。

设 $X_i = 1$ 或 $0$，表示第 $i$ 个零件选或不选。在最大化

$$\dfrac{F+\sum_{i=1}^{n}X_i \cdot F_i}{M+\sum_{i=1}^{n}X_i \cdot M_i}$$

的前提下最小化

$$\sum_{i=1}^{n}X_i \cdot M_i + M.$$

输入格式

第一行是三个用空格分开的正整数 $F,\,M,\,N$。

接下来 $N$ 行，每行两个用空格分开的正整数，第 $i+1$ 行的两个数代表 $F_i$ 和 $M_i$。

输出格式

输出包含 $P$ 行，表示 Bessie 需要安装的 $P$ 个零件的下标。若 Bessie 不需要给这辆车安装零件，输出 NONE。

输出应按递增顺序给出，如果最佳零件集为 $\{2,4,6,7\}$，则输出应按 $2,4,6,7$ 的顺序，而不是 $4,2,7,6$ 的顺序。解决方案将是唯一的。

输入输出样例 #1

输入 #1

1500 100 4 
250 25 
150 9 
120 5 
200 8 

输出 #1

2 
3 
4 

说明/提示

数据范围

$1 \le N \le 10\,000$；

$1 \le M,M_i\le1\,000$；

$1 \le F,F_i \le 1\,000\,000$。

感谢 @tyqtyq 提供的翻译。