1247河中跳房子

【题目描述】

每年奶牛们都要举办各种特殊版本的跳房子比赛包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间有N (0 ≤ N ≤ 50,000) 个岩石每个岩石与起点的距离分别为Di (0 < Di < L)。

在比赛过程中奶牛轮流从起点出发尝试到达终点每一步只能从一个岩石跳到另一个岩石。当然实力不济的奶牛是没有办法完成目标的。

农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行他感到非常厌烦。他计划移走一些岩石使得从起点到终点的过程中最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。

请帮助约翰确定移走这些岩石后最长可能的最短跳跃距离是多少

【输入】

第一行包含三个整数L, N, M相邻两个整数之间用单个空格隔开。

接下来N行每行一个整数表示每个岩石与起点的距离。岩石按与起点距离从近到远给出且不会有两个岩石出现在同一个位置。

【输出】

一个整数最长可能的最短跳跃距离。

【输入样例】

25 5 2

2

11

14

17

21

【输出样例】

4

【提示】

在移除位于2和14的两个岩石之后最短跳跃距离为4从17到21或从21到25。

---

思路

问题:将长度为L的线段中有N个点移除M个点留下N-M个点将整条线段划分为N-M+1个线段。求所有可能的划分方案中最短线段最长的那种方案下最短线段的长度。

方案数有种N达到5 ∗ 10^ 4数量级如果想枚举所有方案求每种方案下的最短线段然后求最大值显然不可行。

逆向思考如果给定点之间最小距离为x即点之间的距离必须x。

需要满足条件为看移除M个点的多种方案中是否存在一种方案其最短线段长度x

而要判断该条件是否成立仍然比较困难。我们可以再逆向思考该命题将其转化为让每条线段长度都x看最少需要移除多少个点。

• 如果移除的点的数量小于等于M则存在一种方案其最短线段长度x条件成立。

• 如果移除的点的数量大于M则不存在这样的方案条件不成立。

清楚要判断的条件后这就是一个二分答案求满足某一条件最大值的问题

求中点mid = (l + r)/2;

如果x满足条件下一次x应该更大取右半边l = mid + 1;

如果x不满足条件下一次x应该更小取左半边r = mid - 1;

最后得到的结果就是要求的各种方案中最短线段的最大值。

需要注意在进行当前枚举的最短距离判断时不能直接用a[i] - a[i - 1]进行判断因为a[i - 1]可能就已经被移走了所以要用一个变量去保存上一块石头的距离当某块石头没被移走就更新下t作为新的距离值

---

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int l,n,m,a[10000001];
bool check(int x)
{
  int t = 0,num = 0;//t:当前观察的点的位置 
  for(int i = 1; i <= n; i++)
    if(a[i] - t < x) num++;
    else t = a[i];//如果点i到当前观察的位置的距离大于等于x则i的位置为当前观察的位置
  if(l - t < x) num++;)//如果终点到观察点距离小于x则移除观察点
  return num <= m;//看移除点的数量是否小于等于M 
}
signed main()
{
  cin>>l>>n>>m;
  for(int i = 1; i <= n; i++) cin>>a[i];
  int le = 0,ri = l,mid;
  while(le + 1 < ri)
  {
    mid = (le + ri) / 2;
    if(check(mid))
    {
      le = mid;
    }
    else
    {
      ri = mid;
    }
  }
  cout<<le;
  return 0;
}