fjutacm 3872 假算法天下第一 二分查找法

算法天下第一 二分查找法"/>

fjutacm 3872 假算法天下第一 二分查找法

Problem Description

one day，Hang is going to pa mount，he see a very beautiful girl

跑题了，Hang最近在练轻功，就是那种可以从第一层台阶跳到第二层台阶的牛逼轻功,为了练习轻功，Hang会进行日常训练，在一条——————这么直的直线上，Hang会先标记处n个点，并计算出每两个点之间的距离，Hang需要从第一个点跳到第n个点。如果你从第l个点跳跃到第r个点，所跳跃的距离为a[l]+a[l+1]+...a[r-2]+a[r-1]，因为Hang比较懒，所以他最多只想跳k下，且每次落点必须在标记的n个点上，请问Hang一次跳跃最少应该跳多远？（可以不跳最远距离，落点必须在标记点上）

Input

第一行是n，k，  1<=n,k<=1e5

第二行n-1个整数，表示a[i]->第i个点到第i+1点的距离 1<=a[i]<=1e5；

Output

输出只有一行，表示每次需要跳的最远距离

SampleInput

6 3 
1 3 2 2 5

SampleOutput

51->3 4
3->5 4
5->6 5
最远距离为5

这题和我写的另一篇博客——割绳子有异曲同工之妙，都是用二分法去查找答案。这题难在思路，有了思路代码还是比较容易实现的。

和割绳子一样我们去二分答案，返回满足条件的答案中，所需步数最多的，也就是题目中的“最少应该跳多远”，即“每次需要跳的最远距离”。读题要读好，这俩一个意思。

再说清楚点，我们要的，是满足条件步数的情况下，尽可能小的步履，也就是我们求出来的答案，要使走完所有a所需步数尽可能大，而不超过k。

因此，要先明确几点。第一，二分的左边界刚好小于a中最大就行，因为你得保证整个过程走得通，否则所需步数就可以看做无穷大，直接pass掉了；右边界刚好大于a的总和就行，因为大很多都一样是一步，没必要浪费时间。至于为什么边界不是等于，可以去看看我 二分板子 博客里分享的另一篇博客，大佬写的。

第二，我的算法是通过判断当前步履大小下，走完全程所需的步数是否大于条件步数，以此来收缩步履大小的边界，所以首先，要让循环一直持续到左右边界交汇，如果res==k我们就return了，不一定能得到最小的步履大小。而正因为一开始松弛了初始区间，用的是“左开右开”的形式，且我们要的是尽可能小的步履，所以最终返回交汇处的r（左边界由于被松弛过了，也就是“开”的边界，所以在交汇处取最小值，是不可取l的）。

然后，上代码，看注释。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <iostream>
#include <string.h>
const int MAX=1e5+5;
using namespace std;
typedef long long ll;
ll a[MAX], maxx, sum;
ll td(int n, ll k)
{ll l=maxx-1, r=sum+1, m, now;int i, j, res;while (l+1<r){res = 0;  /// 初始化当前解所需步数now = 0;  /// 初始化临时跳过的距离m = (l+r)/2;for (i=1; i<n; i++)  /// 遍历一遍柱子{if (now+a[i]>m)  /// 这一跳，跳不到下一根柱子了{now = a[i];   /// 更新位移，从这一根柱子到下一根柱子的距离开始res ++;       /// 这一跳算是在这里结束了，记跳了一次}elsenow += a[i];  /// 能跳过去就加上if (res>k)      /// 步履太小，还没跳完步数就超了，直接可以break准备开始break;        ///下一次循环了}if (now)res ++;  /// 最后一跳也结算一下if (res>k) /// 需要的步数超了，说明步履不够大l = m;else       /// 反之，说明步履大小还有缩小的可能性r = m;}return r;
}
int main()
{ll k;int n, i;cin >> n >> k;maxx = 0;sum = 0;ll ans=0;for (i=1; i<n; i++){scanf("%lld", &a[i]);maxx = max(maxx, a[i]);sum += a[i];}ans = td(n, k);
//  if (ans>maxx) cout << ans << endl;
//  else cout << maxx << endl;cout << ans << endl;return 0;
}