二、越野比賽

1. 審題

題目描述

最近賽車手 $Kaln$ 加入了心心念念的 $Far$ 車隊，馬上就迎來了自己的首秀，參加一場直線加速賽：已知 $Far$ 車隊會提供 $n$ 種類型的賽車，$Kaln$ 只能選擇其中一輛完成比賽，不能中途換車，第 $i$ 輛車踩一次油門所產生的油耗為 $a_i$，能夠行駛的距離為 $b_i$。現給出車隊現在擁有的總油量 $p$，以及車隊提供的車的種數 $n$，和賽道總距離 $m$，請你設計一個小程序，幫助 $Kaln$ 選擇合適的賽車，如果有多輛，按輸入順序輸出，若沒有合適的車，輸出 $?1$。
注意：$Kaln$ 可以在剩余油量足夠的情況下，無限次踩油門。

輸入格式

第一行有三個整數，分別表示 $p,n,m$。
后面 $n$ 行，每行兩個整數，第 $(i+1)$ 行的整數表示第i輛車踩一次油門所產生的油耗為 $a_i$，能夠行駛的距離為 $b_i$。

輸出格式

輸出僅一行，即可以完成比賽的車輛序號，車輛序號即為輸入的第幾輛車，如果有多個，按輸入順序輸出，每兩個序號之間使用空格隔開，若沒有合適的車，輸出 $?1$。

輸入樣例1

100 3 5000
90 0
20 1000
110 10000

輸出樣例 1

2

輸入樣例 2

10 3 5000
20 1000
90 0
110 10000

輸出樣例 2

-1

提示

對于全部的測試點 $1\le p,n,m\le 30000$，$0\le ai,bi\le 1\times 10^5$。

2. 思路

為了更加直觀，我們可以這么命名變量：

int oil; // 總油量
int kind; // 提供車的種類
int S; // 賽道總距離int ri; // 耗油量
int si; // 能夠行駛的距離bool flag = true; // 用于標記是否有合適的車輛

接著我們可以找到幾個特殊的例子，比如：

• 油耗為 $0$ 且能行駛的距離不為 $0$
• 能行駛的距離為 $0$
• 油耗超過總油量

否則，我們才會進行模擬。

		int nowS = 0;int nowOil = oil;while (nowOil >= ri){nowS += si;nowOil -= ri;}if (nowS >= S){cout << i << " ";flag = false;continue;}

3. 參考答案

#include <iostream>
using namespace std;int oil; // 總油量
int kind; // 提供車的種類
int S; // 賽道總距離int ri; // 耗油量
int si; // 能夠行駛的距離bool flag = true; // 用于標記是否有合適的車輛int main()
{// 輸入數據cin >> oil >> kind >> S;for (int i = 1; i <= kind; i++){cin >> ri >> si;// 特殊情況if (ri == 0 && si != 0) // 油耗為0且能行駛的距離不為0{cout << i << " ";flag = false;continue;}if (si == 0) // 能行駛的距離為0{continue;}if (ri > oil) // 油耗超過總油量{continue;}// 模擬int nowS = 0;int nowOil = oil;while (nowOil >= ri){nowS += si;nowOil -= ri;}if (nowS >= S){cout << i << " ";flag = false;continue;}}// 如果沒有合適的車輛if (flag){cout << -1;}return 0;
}