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

版权信息：

任务总览

题目描述

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

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

输入格式

• 第一行输入一个整数t $(1 ≤ t ≤ 10^4)$,
• $10^4$=10x10x10x10=100x100=10000，表示测试用例的个数。
• 对于每个测试用例，输入一行包含两个整数a和b $(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，即：$x≤a−b2$
   • x的最大值就是这个公式的结果，另外还需要考虑x不能超过a，因此最终的x值是： $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个硬币，因此无法存入任何硬币。