AT_awc0002_c.植物の成長観察

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥正在他学校的科学课程中进行一个实验，种植了 $N$ 种不同的植物。

每种植物都有不同的初始高度和每天的生长速度。具体地，第 $i$ 种植物（ $1 \leq i \leq N$ ）在实验开始时（第 $0$ 天）高度为 $A_i$ 厘米，并且每天生长 $B_i$ 厘米。也就是说，第 $i$ 种植物在第 $d$ 天（ $d = 0, 1, 2, \ldots$ ）的高度为 $A_i + B_i \times d$ 厘米。

高桥计划每天（第 $0$ 天、第 $1$ 天、第 $2$ 天、……）检查植物的高度，并且当所有植物高度都至少达到 $M$ 厘米的第一天就结束观察。

请找出结束观察的那一天，也就是最小的非负整数 $d$ ，使得对所有 $i$ （ $1 \leq i \leq N$ ）都有 $A_i + B_i \times d \geq M$ 。

请注意，在给定的约束条件下，保证存在一个有限的答案。

输入格式

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

第一行包含两个整数 $N$ 与 $M$ ，分别代表植物的种数和目标高度，用一个空格隔开。
接下来 $N$ 行，每行包含两个整数，第 $i$ 行（ $1 \leq i \leq N$ ）为第 $i$ 种植物的初始高度 $A_i$ 和每天的生长量 $B_i$ ，用一个空格隔开。

输出格式

请在一行内输出使所有植物高度都至少为 $M$ 厘米的最小非负整数 $d$ 。

输入输出样例

输入#1
```
3 10
2 3
5 2
8 1
```
输出#1
```
3
```
输入#2
```
4 100
100 5
90 10
95 3
80 4
```
输出#2
```
5
```

输入#3

5 1000000000
1 1
500000000 100000000
999999999 1
100000000 300000000
250000000 250000000

输出#3

999999999

说明/提示

数据范围

$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 10^9$
$1 \leq A_i \leq 10^9$
$1 \leq B_i \leq 10^9$
所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页