题解 AT1717 【集合写真】

顾z

2018-07-27 07:58:01

Solution

因为此题给定一个递增序列让我们找一个位置放入一个人(此人身高给定.) 所以我们考虑的做法可以有 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; } ```