[NOIP2015]跳石头

解题报告

原题请见SYZOJ

        关于这道题,当时考场上写的时候,觉得贪心就是正解。然而一下考场,学长告诉我说是二分,当时的我too young too naive, 还不知道二分搜索是什么,如今前来补档。

#include 
#include 
#include 
#include 
#define LL long long
using namespace std;
int l, m, n;
LL sum, le=0, ri, mid;
int d[50005];
inline int get_num()
{
    int ans=0;
    char tmp;
    tmp=getchar();
    while(tmp>'9'||tmp<'0')   tmp=getchar();
    while(tmp>='0'&&tmp<='9')
    {
        ans=ans*10+tmp-48;
        tmp=getchar();
    }
    return ans;
}
inline int check(int a);
int main()
{
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++)
    {
        d[i]=get_num();
        //d[i]=d[i]-sum;
        //sum+=d[i];
    }
    n++;
    d[n]=l;
    ri=l;
    int ans;
    while(le<=ri)
    {
        mid=((ri-le)>>1)+le;
        if(check(mid)<=m)
        {
            le=mid+1;
            ans=mid;
        }
        else
        {
            ri=mid-1;
        }
    }
    cout<

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理