喜欢用自带函数的小盆友们你们好啊，我是简单问题复杂化大师
shy_lihui
·
·
题解
这题很明显可以用自带的sqrt函数不到五秒闪击掉。
但是还可以用二分。
二分的介绍
如果现在要在一个符合单调性的数组里面寻找最小的大于等于某个数的值。
简单地说，有一个符合单调性序列 a_1 \sim a_n，现在有一个数 k，你要找到一个正整数 i，满足 a_i \ge k 且 1 \le i \le n。
如果从前往后枚举时间复杂度 \text{O}(n)，n 大一点得被卡到明年。
我们可以考虑优化，可以每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。
时间复杂度
二分查找的最优时间复杂度为 \text{O}(\log n)。
二分查找的平均时间复杂度和最坏时间复杂度均为
~~摘自 [OIwiki](https://oiwiki.33dai.wiki/basic/binary/)。~~
## 思路分析
$k$ 为最终答案。
左边界为 $1$，右边界大概是 $\sqrt{10^9} \approx 4 \times 10^4 $。
设 $l=1$，$r=40000$，就可以开始二分了。
每次让 $mid=\frac{l+r}{2}$。
如果 $mid^2 \le n$，可以先把 $k$ 设置为 $mid$，如果后续有更优的答案直接替换旧答案即可，然后 $l \to mid+1$，让 $mid$ 往更高的数字尝试。
否则 $r \to mid-1$，$mid$ 过大，往小尝试。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int k;
int n;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
int l=1,r=40000;
while(l<=r)
{
int mid=l+r>>1;//位运算来计算除法，也可以写作 int mid=(l+r)/2;
if(mid*mid<=n)
{
k=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<k;
return 0;
}
```