重庆网站建设套餐,昆明做网站建设方案,网站软件免费下载安装,盐城网站建设流程原题链接#xff1a;https://www.luogu.com.cn/problem/P2678
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
二分答案。#xff08;使用二分需要满足两个条件。一个是有界#xff0c;一个是单调。
这题的题面#xff1a;使得选手们在比赛过程中…原题链接https://www.luogu.com.cn/problem/P2678
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
二分答案。使用二分需要满足两个条件。一个是有界一个是单调。
这题的题面使得选手们在比赛过程中的最短跳跃距离尽可能长。如果题目规定了“最大值最小”或者“最小值最大”的东西那么这个东西应该就满足二分答案的有界性和单调性
定义三个变量dnm分别表示起点到终点的距离起点和终点之间的岩石数以及组委会至多移走的岩石数。开一个数组a数组的第i个元素a[i]表示第i个石头与起点的距离。
定义左边界l0表示起点的石头右边界rd1表示终点的石头。
套用二分模板这里要写一个check()函数。形参x表示当前二分出来的答案。cnt代表计数器记录以当前答案需要移走的实际石头数。i代表下一块石头的编号。now代表当前跳石头的人所在的位置。
写一个while循环这里注意循环结束的条件是in1因为终点那块石头是n1而不是n
判断距离if(a[i]-a[now]x)看二者之间的距离算差值就好。
判定成功把这块石头拿走cnt继续考虑下一块石头。
判定失败这块石头不用拿走我们就跳过去(nowi再考虑下一块。 3. 代码实现
#includebits/stdc.h
using namespace std;
#define ll long long
const int N 50010;
int d, n, m, ans;
int a[N];bool check(int x) { int cnt 0;int i 0, now 0;while (i n 1) {i;if (a[i] - a[now] x) cnt;else now i;}if (cnt m) return false;else return true;
}int main() {cin d n m;for (int i 1; i n; i) cin a[i];int l 0, r d 1;a[0] 0;a[n 1] d;while (l 1 r) {int mid (l r) / 2;if (check(mid)) l mid;else r mid;}cout l endl;return 0;
}
