A1521 | 弹射起步
来源官方 / 2023
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
ac狗不仅可以跑跑，也可以跳跳！
今天ac狗要参加短跑比赛，所有选手从起点出发前往终点，终点与它们的距离为 $n-1$ 个单位长度。比赛虽然叫 "短跑" 比赛，但是并不限制只能用跑的，ac狗比起跑步，更擅长跳跃。
它每 $1$ 秒可以跑动 $1$ 个单位长度，但是也可以花费时间在原地蓄力。例如，当 ac 狗在 $x$ 处蓄力了 $i$ 秒时，它下一次就可以花费 $1$ 秒跳到 $x + i^2$ 处，或者也可以选择继续蓄力。
当然，完成比赛是需要用身体接触红线的，因此ac狗不可以跳过终点（也就是越过 $n$）。
小码君很聪明，在比赛前就可以计算出ac狗最快多少秒可以到达终点，那么这个值是多少呢？
今天ac狗要参加短跑比赛，所有选手从起点出发前往终点，终点与它们的距离为 $n-1$ 个单位长度。比赛虽然叫 "短跑" 比赛，但是并不限制只能用跑的，ac狗比起跑步，更擅长跳跃。
它每 $1$ 秒可以跑动 $1$ 个单位长度，但是也可以花费时间在原地蓄力。例如，当 ac 狗在 $x$ 处蓄力了 $i$ 秒时，它下一次就可以花费 $1$ 秒跳到 $x + i^2$ 处，或者也可以选择继续蓄力。
当然，完成比赛是需要用身体接触红线的，因此ac狗不可以跳过终点（也就是越过 $n$）。
小码君很聪明，在比赛前就可以计算出ac狗最快多少秒可以到达终点，那么这个值是多少呢？
输入格式
输入仅包含一个整数 $n$，表示终点位置。
输出格式
一个整数，表示最少花费的时间。
输入输出样例
输入 #1
1
输出 #1
0
输入 #2
5
输出 #2
3
输入 #3
3
输出 #3
2
输入 #4
114514
输出 #4
363
【样例说明 2】
在起点蓄力两秒，跳跃一秒直接到达终点。
【样例说明 3】
很显然直接跑向终点最优。
【数据范围】
对于前 $25\%$ 的数据，$n \le 20$。
对于前 $50\%$ 的数据，$n \le 100$。
对于前 $75\%$ 的数据，$n \le 10000$。
对于 $100\%$ 的数据，$1 \le n \le 200000$。
在起点蓄力两秒，跳跃一秒直接到达终点。
【样例说明 3】
很显然直接跑向终点最优。
【数据范围】
对于前 $25\%$ 的数据，$n \le 20$。
对于前 $50\%$ 的数据，$n \le 100$。
对于前 $75\%$ 的数据，$n \le 10000$。
对于 $100\%$ 的数据，$1 \le n \le 200000$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？