#10300. Profitable Interest Rate
Profitable Interest Rate
最多存入硬币数 / Maximum Deposit in Profitable Bank
版权信息:
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
最多存入硬币数 | 1 sec | 1024 MB | 100 points |
题目描述
Alice有a
个硬币,她可以选择开启一个“有利可图的”银行存款账户,开启该账户需要至少b
个硬币。还有一个“无利可图”的银行存款账户,只需要任意数量的硬币就能开启,但如果她向“无利可图”的账户存入x
个硬币,那么“有利可图”的账户开启的最低硬币数会减少2 * x
个硬币。
目标是帮助Alice确定她能存入“有利可图”的存款账户的最大硬币数。如果Alice无法开启“有利可图”的账户,则输出0。
输入格式
- 第一行输入一个整数
t
, - =10x10x10x10=100x100=10000,表示测试用例的个数。
- 对于每个测试用例,输入一行包含两个整数
a
和b
,表示Alice拥有的硬币数和开启“有利可图”存款账户所需的最低硬币数。
输出格式
对于每个测试用例,输出一个整数,表示Alice可以存入“有利可图”存款账户的最大硬币数。如果Alice无法开启“有利可图”存款账户,则输出0。
示例
输入示例 1
5
10 5
7 9
5 100
1 1
1 2
输出示例 1
10
5
0
1
0
题目分析
- 直接存入:如果Alice的硬币数
a
大于等于开启“有利可图”存款账户的最低硬币数b
,那么她可以立即存入a
个硬币到“有利可图”的账户。 - 无利可图存款:如果Alice的硬币数
a
小于b
,她可以选择先存x
个硬币到“无利可图”存款账户,这样会使得开启“有利可图”存款账户的要求减少2 * x
个硬币。我们要选择一个合适的x
,使得剩余硬币数足以开启“有利可图”存款账户。 - 关键公式:
- 如果存入
x
个硬币到“无利可图”存款账户后,剩余硬币数为a - x
。 - 这时“有利可图”存款账户的要求变成
b - 2 * x
。 - 为了能开启“有利可图”存款账户,必须满足
a - x >= b - 2 * x
,即: x
的最大值就是这个公式的结果,另外还需要考虑x
不能超过a
,因此最终的x
值是:
- 如果存入
- 计算最大存入的硬币数:
- 最后可以存入的硬币数为
a - x
,即将剩余的硬币存入“有利可图”存款账户。
- 最后可以存入的硬币数为
- 特殊情况:
- 如果
a >= b
,那么Alice可以立即存入所有的硬币。
- 如果
解题思路
- 对于每个测试用例:
- 判断
a
是否大于等于b
,如果是,则输出a
。 - 否则,计算
x
的最大值,并输出a - x
。
- 判断
时间复杂度分析
- 每个测试用例的处理时间是常数级别
O(1)
,因此总时间复杂度为O(t)
,其中t
是测试用例的数量。
空间复杂度分析
- 空间复杂度是
O(t)
,用于存储输入的测试用例以及输出结果。
解释
- 第一组:Alice有10个硬币,且开启“有利可图”存款账户需要5个硬币。Alice可以立即存入所有的10个硬币。
- 第二组:Alice有7个硬币,且开启“有利可图”存款账户需要9个硬币。她可以先存入2个硬币到“无利可图”账户,剩余的5个硬币满足要求,因此可以存入5个硬币。
- 第三组:Alice只有5个硬币,而开启“有利可图”存款账户需要100个硬币,因此无法存入任何硬币。
- 第四组:Alice有1个硬币,且开启“有利可图”存款账户需要1个硬币,直接存入1个硬币。
- 第五组:Alice只有1个硬币,而开启“有利可图”存款账户需要2个硬币,因此无法存入任何硬币。