梦想星际舰队第11关 && FCOI #7 第四题经验题解【原创】
本帖最后由 zhangjinxuan 于 2023-8-20 20:21 编辑梦想星际舰队第11关 && FCOI #7 题解
第四题：经验
题目描述
Ewan-Ahiouy 在玩 《MineCraft》
一开始，他的等级为 0，现在他准备了 n 个附魔之瓶，打算提升自己的等级。
已知从 i 级升到 i+1 级（i∈N*) 需要 i+1 个附魔之瓶，请问他最多会升到多少级？
本题目使用多测，一共有 T 个测试用例。
输入格式
第一行一个整数 T，接下来 T 行，表示每一个测试用例对应的整数 n。
输出格式
一个整数表示答案。
输入输出样例
输入 #1
6
2
3
6
9
19900
114514
输出 #1
1
2
3
3
199
478
数据范围
1≤n≤10^18
1≤T≤2×10^5
其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U321240
答案与解析
**** Hidden Message *****
最佳战士排行榜
**** Hidden Message ***** 根据题目描述，我们需要计算给定的附魔之瓶数量n可以提升到的最高等级。
观察题目中升级等级和所需附魔之瓶数量的规律：
· 升级到1级需要1个附魔之瓶；
· 升级到2级需要2个附魔之瓶；
· 升级到3级需要3个附魔之瓶；
· ...
· 升级到i级需要i个附魔之瓶。
可以观察到，当附魔之瓶数量n满足 1+2+3+...+k <= n 时，最高可以升级到k级。而当 1+2+3+...+k > n 时，最高只能升级到k-1级。
通过求解等差数列的和，可以使用以下公式计算等级k：
k = int(sqrt(2 * n + 0.25) - 0.5)
使用Python代码实现如下：
import math
def calcMaxLevel(n):
k = int(math.sqrt(2 * n + 0.25) - 0.5)
return k
T = int(input())
for _ in range(T):
n = int(input())
result = calcMaxLevel(n)
print(result)
希望对您有所帮助！如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案 根据题目描述，Ewan-Ahiouy想要通过使用附魔之瓶来提升他的等级。已知从第i级升到第i+1级需要i+1个附魔之瓶。题目要求我们计算他最多能升到多少级。
我们可以观察到，当Ewan-Ahiouy拥有的附魔之瓶数量为n时，他最多可以升到的级数是连续的。也就是说，他能升到的最高级数是满足以下条件的最大的i：1+2+3+...+i <= n。
为了计算这个最大的i，我们可以使用二分查找的方法。首先，我们设置一个左边界l=0和一个右边界r=n。然后，我们在的范围内进行二分查找，直到找到最大的i满足1+2+3+...+i <= n。
具体的二分查找过程如下：
1. 初始化l=0和r=n。
2. 当l <= r时，执行以下步骤：
· 计算中间值mid = (l + r) // 2。
· 计算1+2+3+...+mid的和sum = (mid * (mid + 1)) // 2。
· 如果sum <= n，说明mid满足条件，更新l = mid + 1。
· 否则，更新r = mid - 1。
3. 返回r作为最大的满足条件的i。
下面是实现这个算法的Python代码：
def max_level(n):
l, r = 0, n
while l <= r:
mid = (l + r) // 2
sum = (mid * (mid + 1)) // 2
if sum <= n:
l = mid + 1
else:
r = mid - 1
return r
T = int(input())
for _ in range(T):
n = int(input())
print(max_level(n))
这个代码首先读取输入的测试用例数量T，然后依次读取每个测试用例的附魔之瓶数量n，并调用max_level函数计算最大的满足条件的等级，并将结果打印出来。
希望这个解答对你有帮助！ 看看 陈尚涵 发表于 2023-8-20 19:11
看看
我也看看 天才！{:10_257:}我还不会一元二次方程{:10_266:} isdkz 发表于 2023-8-20 19:04
根据题目描述，Ewan-Ahiouy想要通过使用附魔之瓶来提升他的等级。已知从第i级升到第i+1级需要i+1个附魔之瓶 ...
{:10_306:} Ewan-Ahiouy 发表于 2023-8-20 19:28
天才！我还不会一元二次方程
这个，几个公式就行了 Ewan-Ahiouy 发表于 2023-8-20 19:29
二分也正解 陈尚涵 发表于 2023-8-20 19:33
这个，几个公式就行了
问号脸.jpg import math
T = int(input())
for i in range(T):
n = int(input())
a = 1
b = 1
c = -2 * n
x = int((-b + math.sqrt(b**2 - 4*a*c)) / (2*a))
print(x)
页:
[1]