#10300. Profitable Interest Rate

Profitable Interest Rate

最多存入硬币数 / Maximum Deposit in Profitable Bank

版权信息:

image

任务总览

任务名称 时间限制 内存限制 分数
最多存入硬币数 1 sec 1024 MB 100 points

题目描述

Alice有a个硬币,她可以选择开启一个“有利可图的”银行存款账户,开启该账户需要至少b个硬币。还有一个“无利可图”的银行存款账户,只需要任意数量的硬币就能开启,但如果她向“无利可图”的账户存入x个硬币,那么“有利可图”的账户开启的最低硬币数会减少2 * x个硬币。

目标是帮助Alice确定她能存入“有利可图”的存款账户的最大硬币数。如果Alice无法开启“有利可图”的账户,则输出0。

输入格式

  • 第一行输入一个整数t (1t104)(1 ≤ t ≤ 10^4),
  • 10410^4=10x10x10x10=100x100=10000,表示测试用例的个数。
  • 对于每个测试用例,输入一行包含两个整数ab (1a,b109)=10亿(1 ≤ a, b ≤ 10^9)=10亿,表示Alice拥有的硬币数和开启“有利可图”存款账户所需的最低硬币数。

输出格式

对于每个测试用例,输出一个整数,表示Alice可以存入“有利可图”存款账户的最大硬币数。如果Alice无法开启“有利可图”存款账户,则输出0。

示例

输入示例 1

5
10 5
7 9
5 100
1 1
1 2

输出示例 1

10
5
0
1
0

题目分析

  1. 直接存入​:如果Alice的硬币数a大于等于开启“有利可图”存款账户的最低硬币数b,那么她可以立即存入a个硬币到“有利可图”的账户。
  2. 无利可图存款​:如果Alice的硬币数a小于b,她可以选择先存x个硬币到“无利可图”存款账户,这样会使得开启“有利可图”存款账户的要求减少2 * x个硬币。我们要选择一个合适的x,使得剩余硬币数足以开启“有利可图”存款账户。
  3. 关键公式​:
    • 如果存入x个硬币到“无利可图”存款账户后,剩余硬币数为a - x
    • 这时“有利可图”存款账户的要求变成b - 2 * x
    • 为了能开启“有利可图”存款账户,必须满足 a - x >= b - 2 * x,即:xab2 x≤a−b2
    • x的最大值就是这个公式的结果,另外还需要考虑x不能超过a,因此最终的x值是: x=min(ab2,a)x = \min\left( \frac{a - b}{2}, a \right)
  4. 计算最大存入的硬币数​:
    • 最后可以存入的硬币数为 a - x,即将剩余的硬币存入“有利可图”存款账户。
  5. 特殊情况​:
    • 如果a >= b,那么Alice可以立即存入所有的硬币。

解题思路

  • 对于每个测试用例:
    1. 判断a是否大于等于b,如果是,则输出a
    2. 否则,计算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个硬币,因此无法存入任何硬币。