AT_abc356_g.[ABC356G] Freestyle

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

高桥可以游出 $N$ 种不同的风格。
当他用第 $i$ 式游泳时，每秒消耗 $A_i$ 体力，每秒前进 $B_i$ 米。

回答 $Q$ 个问题。第 $i$ 次查询如下：

判断是否有可能在总体力消耗不超过 $C_i$ 的情况下前进 $D_i$ 米。如果可能，请找出所需的最少秒数。

在这里，他可以自由组合不同的泳姿，切换泳姿的时间可以忽略不计。
具体来说，他可以使用以下步骤游泳：

选择一个正整数 $m$ ，一个长度为 $m$ 的正实数序列 $t=(t_1,t_2,\dots,t_m)$ ，以及一个长度为 $m$ 的整数序列 $x=(x_1,x_2,\dots,x_m)$ ，其中每个元素都介于 $1$ 和 $N$ 之间（含）。
然后，按照 $i=1,2,\dots,m$ 的顺序，以第 $x_i$ 的方式游 $t_i$ 秒。

输入格式

输入内容由标准输入法提供，格式如下

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

$Q$

$C_1$ $D_1$

$C_2$ $D_2$

$\vdots$

$C_Q$ $D_Q$

输出格式

共输出 $Q$ 行。
对于第 $i$ 次查询，在第 $i$ 行输出答案如下：

如果不可能前进 $D_i$ 米，同时保持体力消耗总量不超过 $C_i$ ，则输出 -1。
否则，输出所需的最短时间。如果输出值与真实答案之间的绝对或相对误差不超过 $10^{-9}$ ，则认为输出正确。

输入输出样例

输入#1

输出#1

3.000000000000000000
1.750000000000000000
-1
125.000000000000000000
1.500000000000000000

说明/提示

限制因素

所有输入值均为整数。
$1 \le N \le 2 \times 10^5$
$1 \le A_i, B_i \le 10^9$
$1 \le Q \le 2 \times 10^5$
$1 \le C_i, D_i \le 10^9$

样例 $1$ 说明

在此输入中，高桥可以用以下四种方式游泳：

消耗 $1$ 体力，每秒前进 $2$ 米。
消耗 $2$ 体力，每秒前进 $3$ 米。
消耗 $3$ 体力，每秒前进 $3$ 米。
消耗 $4$ 体力，每秒前进 $4$ 米。

此输入包含五个查询。

第一个查询， $C_1=4, D_1=7$ $C_{1} = 4, D_{1} = 7$ 。
- 选择 $t=(1,2)$ $t = (1, 2)$ 和 $x=(2,1)$ $x = (2, 1)$ 。高桥游泳的过程如下：
  - 在前 $1$ 秒，他消耗了 $2$ 体力，前进了 $3$ 米。
  - 接下来的 $2$ 秒，他消耗了 $2$ 体力，前进了 $4$ 米。
- 他总共消耗了 $4$ 体力，前进了 $7$ 米。所需的时间为 $3$ 秒，这是最小值。
第二个查询， $C_2=7, D_2=7$ $C_{2} = 7, D_{2} = 7$ 。
- 选择 $t=(7/4)$ $t = (7/4)$ 和 $x=(4)$ $x = (4)$ 。高桥游程如下：
  - 在最初的 $7/4$ 秒内，他消耗了 $7$ 体力，前进了 $7$ 米。
- 他总共消耗了 $7$ 体力，前进了 $7$ 米。所需的时间为 $7/4$ 秒，这是最小值。
第三个查询， $C_3=49, D_3=100$ $C_{3} = 49, D_{3} = 100$ 。
- 无论高桥如何游泳，都不可能在总体力消耗不超过 $49$ 的情况下前进 $100$ 米。
第四个查询， $C_4=1000, D_4=500$ $C_{4} = 1000, D_{4} = 500$ 。
- 选择 $t=(125)$ $t = (125)$ 和 $x=(4)$ $x = (4)$ 。高桥游泳的情况如下：
  - 在前 $125$ 秒，他消耗了 $500$ 体力，前进了 $500$ 米。
- 他总共消耗了 $500$ 体力，前进了 $500$ 米。所需的时间为 $125$ 秒，这是最小值。
第五个查询， $C_5=4, D_5=5$ $C_{5} = 4, D_{5} = 5$ 。
- 选择 $t=(1/2,1)$ $t = (1/2, 1)$ 和 $x=(4,2)$ $x = (4, 2)$ 。高桥游程如下：
  - 在前 $1/2$ 秒，他消耗了 $2$ 体力，前进了 $2$ 米。
  - 在接下来的 $1$ 秒内，他消耗了 $2$ 点体力，前进了 $3$ 米。
- 他总共消耗了 $4$ 体力，前进了 $5$ 米。所需的时间为 $3/2$ 秒，这是最短时间。

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

首页