UPC Go Home(贪心 || 前缀和+二分)(STL二分函数的使用)

网友投稿 220 2022-09-21

UPC Go Home(贪心 || 前缀和+二分)(STL二分函数的使用)

Go Home

题目描述 There is a kangaroo at coordinate 0 on an infinite number line that runs from left to right, at time 0. During the period between time i−1 and time i, the kangaroo can either stay at his position, or perform a jump of length exactly i to the left or to the right. That is, if his coordinate at time i−1 is x, he can be at coordinate x−i, x or x+i at time i. The kangaroo’s nest is at coordinate X, and he wants to travel to coordinate X as fast as possible. Find the earliest possible time to reach coordinate X.

Constraints X is an integer. 1≤X≤109

输入 The input is given from Standard Input in the following format: X输出 Print the earliest possible time for the kangaroo to reach coordinate X.样例输入 Copy 6样例输出 Copy 3提示 The kangaroo can reach his nest at time 3 by jumping to the right three times, which is the earliest possible time.

题意: 从原点出发,在时间i可以走i的路程,可以向左向右或不动。问到达x的最短时间。思路: (1)贪心:一直往右走是时间最短的。会有两种情况:在i时恰好到达x,或在i时超过x;对于前者一定是最短时间,对于后者我们可以在时间i之前选择往左走,从而使i时恰好到达x;这也就引出了方法二 (2)前缀和+二分:基于(1)的分析我们可以维护一个前缀和数组。找数组中第一个>=x的位置即可。代码: (1)贪心(模拟)

#includeusing namespace std;int x,start;void solve(){ cin>>x; for(int i=1;i<=x;i++){ start+=i; if(start>=x){ cout<

(2)前缀和+二分(手写二分)

#includeusing namespace std;const int maxn=50000;int a[maxn],x;void solve(){ for(int i=1;i>x; int l=0,r=maxn-1,res=0; while(l<=r){ int mid=l+(r-l)/2; if(a[mid]>=x) r=mid-1; else if(a[mid]

(3)STL 二分

#includeusing namespace std;const int maxn=50000;int a[maxn],x;void solve(){ for(int i=1;i>x; int ans=lower_bound(a,a+maxn,x)-a; cout<

知识补充:1.如果用mid=(left+right)/2,如果right是int上限一半还多,那么可能导致溢出,使用mid=left+(right-left)/2可以代替以避免溢出2.lower_bound(first,last,val)函数在[first,last)进行二分查找返回大于或等于val的第一个元素的位置,如果是数组,返回该位置指针,若没有则返回last的位置。upper_bound()与lower_bound()相似,查找的是第一个大于val的元素的位置。举个栗子0v0:数组a={1,2,4,4,4,5,7,9,9,10,13,17},想查找4第一次出现位置,lower_bound(a,a+n,4)-a,返回值是2.

参考资料: ​​二分总结_​​​​算法复习——二分(二分查找,stl lower_bound()、upper_bound()木棒切割,快速幂)​​

保持热爱,奔赴山海。

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:015解决父级边框塌陷问题
下一篇:王海:罗永浩第一次“认怂”的男人!
相关文章

 发表评论

暂时没有评论,来抢沙发吧~