109徐守佳

用户名：dotcpp0787174

访问量：995

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	919
经　　验	3474
参赛次数	1
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

[蓝桥杯算法提高VIP-种树] - 我搜搜搜搜搜
浏览：46

[蓝桥杯2017年第八届真题-油漆面积] 扫描线
浏览：40

二分直接用现成的STL:lower_bound/upper_bound(新增手写二分)
浏览：59

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

[信息学奥赛一本通T1247-河中跳房子] 二分答案

　　作者: 109徐守佳　　　　发表时间：2024-10-13 01:30:17 浏览：41　|　评论：0　

原题链接：信息学奥赛一本通T1247-河中跳房子

```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define PII pair<int,int>
using namespace std;
const int N =  1 *1e7 + 10,M = 5 * 1e4 + 10,inf = 0x3f3f3f3f;

int len,n,m;
int dis[M];
//在搬完所有石头后,设当前跳跃的距离能够跳完为1,不能跳跃完的情况为0,答案区间为[0,0,0,0,0,1,1,1,1,1,1,1]
//而我们需要找到第一个1的位置,所以区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
void solve()
{
    cin>>len>>n>>m;
    for(int i=1;i<=n;i++) //输入第i个石头到起点的距离;
    {
        cin>>dis[i];
    }
    dis[n+1] = len; //最后一个石头设为len
    int mid,l=-1e9-10,r=1e9+10; //设置二分左右起点
    while (l < r) //区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
    {
        int mid = l+r+1 >> 1; //跳的距离
        int cnt = 0 , now = 0; //cnt代表搬走了几块石头,now代表当前在的位置
        for(int i=1;i<=n+1;i++)
        {
            //dis[i] 
            if(dis[i] - now < mid ) cnt++; 
            //如果当前下一个石头和当前位置差距小于我们设置的跳跃的距离,搬走它,尝试挑战下一个石头
            else now = dis[i]; //实在不行就跳在上面嘛
        }

if(cnt > m) r = mid-1; 
        //搬的石头大于我们题目要求的,说明我们设置的跳跃距离过大了,在[l,mid-1]那边去找
        else l = mid;
    }
    cout<<r<<endl;
    
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.13 00:45:51
 */
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

109徐守佳

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C二级辅导-计负均正（C语言代码）

汽水瓶（C++代码）（直接n/2就可以了）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

[信息学奥赛一本通T1247-河中跳房子] 二分答案

评论区

精彩推荐

汽水瓶（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

printf基础练习（C语言代码）

非常简单的算法，题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

【计算两点间的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

109徐守佳

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C二级辅导-计负均正 （C语言代码）

汽水瓶 （C++代码）（直接n/2就可以了）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

[信息学奥赛一本通T1247-河中跳房子] 二分答案

评论区

精彩推荐

汽水瓶 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

printf基础练习 （C语言代码）

非常简单的算法，题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

【计算两点间的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C二级辅导-计负均正（C语言代码）

汽水瓶（C++代码）（直接n/2就可以了）

　　评论区

汽水瓶（C语言代码）

printf基础练习（C语言代码）

【计算两点间的距离】（C语言代码）