题解 AT1717 【集合写真】
顾z
2018-07-27 07:58:01
因为此题给定一个递增序列让我们找一个位置放入一个人(此人身高给定.)
所以我们考虑的做法可以有
1.插入排序
2.二分查找
3.sort
这里送上二分查找做法 :
规定左右两端边界,low,high,每次求mid位置
然后我们可以比较进来人的身高与
当前mid位置人的身高的大小位置关系
因为序列是递增的
所以我们可以缩减区间范围.
从而我们可以一步一步的逼近该有的位置
需要注意的地方:
1.岛国的题末尾要加(重点:换行符 !
2.区间范围限制 (要不然会死循环 !
送上我优(chou)美(lou)的代码
```cpp
#include<bits/stdc++.h>//万能库
#define RI register int//register加速
int n,I,low,high;
int height[55];
int main()
{
std::cin>>n;
for(RI i=1;i<=n;i++)std::cin>>height[i];
std::cin>>I;//需要进去的人的身高
low=1,high=n;
while(low<=high)//区间范围限制
{
int mid=low+high>>1;
if(height[mid]>I)high=mid-1;
else low=mid+1;
//根据上面的 就是缩减区间范围
//如果mid位置人的身高比我高,
//那我就缩减一下右端范围
//左端同理
}
std::cout<<low;
}
```