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

简介: 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)贪心(模拟)

#include<bits/stdc++.h>
using namespace std;
int x,start;
void solve(){
    cin>>x;
    for(int i=1;i<=x;i++){
        start+=i;
        if(start>=x){
            cout<<i<<endl;
            break;
        }
    }
}
int main(){
    solve();
    return 0;
}

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

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000;
int a[maxn],x;
void solve(){
    for(int i=1;i<maxn;i++) a[i]=a[i-1]+i;
    cin>>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]<x)l=mid+1;
    }
    cout<<l<<endl;
}
int cutele(){
    solve();
    return 0;
}

(3)STL 二分

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000;
int a[maxn],x;
void solve(){
    for(int i=1;i<maxn;i++) a[i]=a[i-1]+i;
    cin>>x;
    int ans=lower_bound(a,a+maxn,x)-a;
    cout<<ans<<endl;
}
int cutele(){
    solve();
    return 0;
}

知识补充:

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()木棒切割,快速幂)


保持热爱,奔赴山海。

目录
相关文章
|
17天前
|
JSON 安全 网络协议
go语言使用内置函数和标准库
【10月更文挑战第18天】
13 3
|
6月前
|
存储 算法 Go
go语言中的延迟执行函数
【5月更文挑战第13天】`defer`是Go语言中用于延迟执行函数的关键字,尤其适用于资源管理,如文件关闭和锁的释放。它在函数返回前按照LIFO顺序执行,确保资源在任何返回路径下都能正确释放。`defer`可以拦截`panic`并在函数返回前执行,但无法阻止某些致命的`panic`。此外,`defer`可用于修改返回值、输出调试信息和还原变量值。尽管在某些场景下可能影响性能,但Go的优化使得其在多数情况下性能表现良好,特别是在资源清理方面。在Go 1.20及以后的版本,`defer`的性能已显著提升,尤其是在高计算量的场景下。
273 2
|
2月前
|
Go
go函数
go函数
33 10
|
2月前
|
编译器 Go C++
Go to Learn Go之函数
Go to Learn Go之函数
28 0
|
2月前
|
编译器 Go 索引
Go数组、多维数组和切片(动态数组),及常用函数len(),cap(),copy(),append()在切片中的使用
本文介绍了Go语言中数组、多维数组和切片(动态数组)的基本概念和操作,包括数组的定义、初始化、访问,多维数组的定义和访问,以及切片的创建、使用和扩容。同时,还讲解了切片中常用的函数len()、cap()、copy()和append()的使用方法。
|
3月前
|
Prometheus Cloud Native Go
Go 1.22 标准库 slices 新增函数和一些旧函数增加新特性
Go 1.22 标准库 slices 新增函数和一些旧函数增加新特性
|
3月前
|
安全 编译器 Go
Go 1.21: 泛型函数的全面回顾
Go 1.21: 泛型函数的全面回顾
|
3月前
|
Go
深入理解 Go 中的 new() 和 make() 函数
深入理解 Go 中的 new() 和 make() 函数
|
3月前
|
设计模式 Java 数据库连接
|
3月前
|
Go 开发者