洛谷P2768

news/2025/2/14 16:16:09/

二分真的好难/(ㄒoㄒ)/~~!

首先看题,题目中我们可以知道选手跳跃最短距离的最大值,所以我们可以使用二分。

判断是否需要二分可以看题目中是否有类似求最短距离的最大值或者最大距离的最小值。

那么本题怎么进行二分呢

我们可以以整段距离为一个大区间,然后二分取其中间值,用其中间值来暂时当作一个最大的最小跳跃距离,以此来求需要搬掉几块石头。如果石头搬多了那么说明我们选择的值太大,搬少了,说明我们选择的值太小。最后两个端点就可以确定同一个值了。

废话不多说,上代码:

#include <bits/stdc++.h>
#define LL long longusing namespace std;
const int N = 5 * 1e4 + 10;
//typedef long long LL;
int l, n, m, ans;
int d[N];
//二分模板一般时比较固定的,但是难就难在中间的check函数上inline int read()//快读不解释
{int sum = 0;char ch = getchar();while (ch > '9' || ch < '0') ch = getchar();while (ch <= '9' && ch >= '0')sum = sum * 10 + ch - 48, ch = getchar();return sum;
}bool check(int x)//x为中间值
{int cnt = 0;//判断移去的石头的数量int next = 0;//下一块石头的位置int now = 0;//运动员所处的位置while (next < n + 1){next++;if (d[next] - d[now] < x)//如果两块石头的位置小于我们需要的x,则可以搬掉next所在的这个石头,运动员位置保持不变来判断下一块。{cnt++;//搬掉了一块石头}elsenow = next;//中间距离超过了我们现在的最大的最小距离,则不能搬,运动员到这个石头的位置}if (cnt > m)//看看搬的石头是多还是少return false;elsereturn true;
}int main()
{l = read(), n = read(), m = read();for (int i = 1; i <= n; ++i){d[i] = read();}d[n + 1] = l;int rl = 1, r = l;//rl为左端点,r为右端点while (rl <= r)//二分模板{int mid = (rl + r) / 2;if (check(mid))//值太小,搬少了或者搬得刚刚好{ans = mid;//暂时存到这里,看看有没有更好的解rl = mid + 1;}else//值太大,搬少了r = mid - 1;}cout << ans << endl;//最后的答案return 0;
}


http://www.ppmy.cn/news/628802.html

相关文章

Buffalo框架的使用

【整体介绍&#xff0c;建议先看完下面的内容在回过来看这个介绍】当用户输入账号密码后&#xff0c;点击“提交”按钮&#xff0c;则执行JSh中的getInfo()方法&#xff0c;该方法会调用Buffalo框架中的remoteCall("UserService.getInfo",[username,password],functi…

洛谷 AT_abc178_b [ABC178B] Product Max

洛谷 AT_abc178_b [ABC178B] Product Max 1、题目题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示制約Sample Explanation 1Sample Explanation 2 2、翻译题面&#xff1a; AC代码&#xff…

洛谷P1077摆花

文章目录 一、题目描述二、思路三、代码 一、题目描述 https://www.luogu.com.cn/problem/P1077 题目描述很容易看懂 二、思路 动态规划题目&#xff0c;首先定义状态 dp[i][j]:摆前i种花&#xff0c;一共摆j盆的方案数。 i&#xff1a;1~n j&#xff1a;1~m 需要注意的时&a…

IP地点定位为什么有误差?

随着互联网的不断普及&#xff0c;人们对IP地点定位需求越来越多。然而&#xff0c;即便是在现代技术的支持下IP地点定位仍然存在误差。那么&#xff0c;IP地点定位为什么会出现误差呢&#xff1f; IP&#xff08;Internet Protocol&#xff09;地址是指互联网协议&#xff08;…

数据库技术之MySQL高级

目录 子查询与表连接 子查询(嵌套sql) 利⽤⼦查询进⾏过滤 作为计算字段使⽤⼦查询 外键 表关系 关系表 表联结 联结多个表 使⽤表别名 AS 组合查询 UNION 总结&#xff1a;表联结 练习题 sql_mode sql_mode值的含义 MySQL事务 概述 ⼀,事务的语法 ⼆,事务的…

一篇博客帮你了解MySQL高级知识

MySQL高级 一、子查询与表连接子查询&#xff08;嵌套SQL&#xff09;关系表组合查询 UNION 二、MySQL事务概述事务的语法事务的ACID特性事物的并发问题事物的的隔离级别不同隔离级别的锁的情况&#xff08;了解&#xff09;隐式提交&#xff08;了解&#xff09; 三、MySQL中的…

构建高并发平台架构

一、 设计理念 1. 空间换时间 1) 多级缓存&#xff0c;静态化 客户端页面缓存&#xff08;http header中包含Expires/Cache of Control&#xff0c;last modified(304&#xff0c;server不返回body&#xff0c;客户端可以继续用cache&#xff0c;减少流量)&#xf…

高并发高可用的 架构实践

高并发高可用的 架构实践 一、 设计理念 1.空间换时间 1)多级缓存&#xff0c;静态化 客户端页面缓存&#xff08;http header中包含Expires/Cache of Control&#xff0c;last modified(304&#xff0c;server不返回body&#xff0c;客户端可以继续用cache&#xff0c;减少流量…