题解 P2678 【跳石头】

· · 题解

本蒟蒻第一篇题解

首先说下本题思路：

1.看数据：显然n^2不可能，于是想到nlogn。

2.分析复杂度：logn肯定与排序，二分，堆有关，输入数据本来就有序，不用排序；堆，也用来做排序之类的工作，于是排除；所以用二分答案。

3.怎么验证：每次求当前石头与上一个有效的石头距离，然后与而二分数据比较看是否去掉，若去掉，计数器加一，最后再判断一下是否在要求范围内就可以了。

P.S: 坑点：题目中说的L是有用的，表示最后一个石头（终点）与起点的距离！！（我调了1个小时）

看代码吧：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <cstring>   //本人不喜欢万能头文件。。
using namespace std;
int k, m, n, a[1000005];
inline int read() {
    int ch = getchar();
    while (ch > '9' || ch < '0')ch = getchar();
    int num = ch - '0';
    ch = getchar();
    while (ch >= '0' && ch <= '9') {
        num *= 10;
        num += ch - '0';
        ch = getchar();
    }
    return num;
}                             //快读是个好习惯
inline bool check(int x) {   //贪心验证二分
    int num = 0, now = 0;   //num记录挪开石头数
    for (register int i = 1; i <= n + 1; i++)     {
        if (a[i] - a[now] >= x) 
            now = i;
        else //挪开
            num++;
    }
    if (num <= m)return true;//判定是否符合标准
    return false;
}
int main() {
    k = read();
    n = read();
    m = read();
    for (register int i = 1; i <= n; i++) {
        a[i] = read();
    }//读入数据
    a[n + 1] = k;  //终点石头也要算！！
    int l = 0, r = k, mid, ans;//ans为答案
    while (l <= r) {  //二分答案
        mid = (l + r) / 2;
        if (check(mid) == true) {
            l = mid + 1;
            ans = mid;
        }
        else
            r = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

管理大大求过！！