[已解决]梦想星际舰队第11关 && FCOI #7 第四题经验题解【原创】

zhangjinxuan

梦想星际舰队第11关 && FCOI #7 题解

第四题：经验

题目描述

Ewan-Ahiouy 在玩 《MineCraft》

一开始，他的等级为 0，现在他准备了 n 个附魔之瓶，打算提升自己的等级。

已知从 i 级升到 i+1 级（i∈N*) 需要 i+1 个附魔之瓶，请问他最多会升到多少级？

本题目使用多测，一共有 T 个测试用例。

输入格式
第一行一个整数 T，接下来 T 行，表示每一个测试用例对应的整数 n。

输出格式
一个整数表示答案。

输入输出样例
输入 #1

1. 6
   
2. 2
   
3. 3
   
4. 6
   
5. 9
   
6. 19900
   
7. 114514

复制代码

输出 #1

1. 1
   
2. 2
   
3. 3
   
4. 3
   
5. 199
   
6. 478

复制代码

数据范围

1≤n≤10^18
1≤T≤2×10^5

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U321240

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士排行榜

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-8-20 20:14:39

1. import math
   
2. T = int(input())
   
3. for i in range(T):
   
4.     n = int(input())
   
5.     a = 1
   
6.     b = 1
   
7.     c = -2 * n
   
8.     x = int((-b + math.sqrt(b**2 - 4*a*c)) / (2*a))
   
9.     print(x)
   

复制代码

跳转到最佳答案楼层

陶远航

根据题目描述，我们需要计算给定的附魔之瓶数量n可以提升到的最高等级。

观察题目中升级等级和所需附魔之瓶数量的规律：
· 升级到1级需要1个附魔之瓶；
· 升级到2级需要2个附魔之瓶；
· 升级到3级需要3个附魔之瓶；
· ...
· 升级到i级需要i个附魔之瓶。

可以观察到，当附魔之瓶数量n满足 1+2+3+...+k <= n 时，最高可以升级到k级。而当 1+2+3+...+k > n 时，最高只能升级到k-1级。

通过求解等差数列的和，可以使用以下公式计算等级k：

1. k = int(sqrt(2 * n + 0.25) - 0.5)
   

复制代码

使用Python代码实现如下：

1. import math
   
2. 
   
3. def calcMaxLevel(n):
   
4.     k = int(math.sqrt(2 * n + 0.25) - 0.5)
   
5.     return k
   
6. 
   
7. T = int(input())
   
8. for _ in range(T):
   
9.     n = int(input())
   
10.     result = calcMaxLevel(n)
    
11.     print(result)
    

复制代码

希望对您有所帮助！如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案

isdkz

根据题目描述，Ewan-Ahiouy想要通过使用附魔之瓶来提升他的等级。已知从第i级升到第i+1级需要i+1个附魔之瓶。题目要求我们计算他最多能升到多少级。

我们可以观察到，当Ewan-Ahiouy拥有的附魔之瓶数量为n时，他最多可以升到的级数是连续的。也就是说，他能升到的最高级数是满足以下条件的最大的i：1+2+3+...+i <= n。

为了计算这个最大的i，我们可以使用二分查找的方法。首先，我们设置一个左边界l=0和一个右边界r=n。然后，我们在[l, r]的范围内进行二分查找，直到找到最大的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代码：

1. def max_level(n):
   
2.     l, r = 0, n
   
3.     while l <= r:
   
4.         mid = (l + r) // 2
   
5.         sum = (mid * (mid + 1)) // 2
   
6.         if sum <= n:
   
7.             l = mid + 1
   
8.         else:
   
9.             r = mid - 1
   
10.     return r
    
11. 
    
12. T = int(input())
    
13. for _ in range(T):
    
14.     n = int(input())
    
15.     print(max_level(n))
    

复制代码

这个代码首先读取输入的测试用例数量T，然后依次读取每个测试用例的附魔之瓶数量n，并调用max_level函数计算最大的满足条件的等级，并将结果打印出来。

希望这个解答对你有帮助！

陈尚涵

看看

Ewan-Ahiouy

陈尚涵 发表于 2023-8-20 19:11
看看

我也看看

Ewan-Ahiouy

天才！我还不会一元二次方程

Ewan-Ahiouy

isdkz 发表于 2023-8-20 19:04
根据题目描述，Ewan-Ahiouy想要通过使用附魔之瓶来提升他的等级。已知从第i级升到第i+1级需要i+1个附魔之瓶 ...

陈尚涵

Ewan-Ahiouy 发表于 2023-8-20 19:28
天才！我还不会一元二次方程

这个，几个公式就行了

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-20 19:29

二分也正解

Ewan-Ahiouy

陈尚涵 发表于 2023-8-20 19:33
这个，几个公式就行了

问号脸.jpg

sfqxx

1. import math
   
2. T = int(input())
   
3. for i in range(T):
   
4.     n = int(input())
   
5.     a = 1
   
6.     b = 1
   
7.     c = -2 * n
   
8.     x = int((-b + math.sqrt(b**2 - 4*a*c)) / (2*a))
   
9.     print(x)
   

复制代码