二分
作者:
二十四_5
,
2021-09-03 23:38:31
,
所有人可见
,
阅读 337
题意理解:
题目的意思很简单,就是最多移走m块石头,使得选手跳跃的最短距离最大即可。
主要思路:
二分答案->->从起点出发,先选定一段距离mid,若前面的石头B与你所站着的石头A的距离小于mid,就把B搬掉,记录一下;如果不,就把B留下,再跳到石头B上。照这个步骤多次循环后,如果搬掉的石头多了,就把距离mid定小点;如果少了,就把mid定大点。
重点注意一下数组下标从1开始,因为是到起点的距离,起点即为q[0]=0
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4+10;
int length,n,flag;
int q[N],ans;
int main()
{
cin >> length >> n >> flag;
for (int i = 1; i <= n; i ++ ) cin >> q[i];//从1是因为数组是距离原点0的距离,即q[0]=0
int l = 0 , r = length;
while(l <= r)
{
int mid = (l + r) / 2;
int s = 0,now = 0;//now从0开始就是从第一个数组元素和原点的的距离
for (int i = 1; i <= n; i ++ )
{
if(q[i]-q[now] < mid) s ++;
else now = i;
}
if(s <= flag)
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
cout << ans << endl;
return 0;
}
没有题解吗
主要就是自己回头复习看看hh