题解 P1316 【丢瓶盖】

· · 题解

update 2019.11.3,我觉得我写的不够好，今天有时间更新一下。我认为题解应该教会读者一个算法，而不是只一道题。

一个故事

在minecraft中，从高往低跳，请问至少站在多少层才会死？（同时我知道在1024层往下跳一定会死）

只有傻逼才会这样做：第一层往下跳，活着；第二层往下跳，活着；第三层往下跳，活着；

可以发现，这个序列是：活活活活活活活活活活活活活活活活活活活活活……死死死死死死死死死死死死死死死死，只要找到第一个“死”就好了！

我们可以这样做：从（1 + 1024）/2 = 512 层往下跳如果活着，那么正确答案一定在513~1024中；反之512 层往下跳如果死了那么正确答案一定在512~1中。反复进行此过程，就能得到正确答案。

我们可以得到一个重要的结论：如果想二分的话，一定要找到单调性，如下图。

当然，还单调性为可以这样：

像这样的就不能二分答案：

对于这一题，我画个图你就知道了（当然，这可能不为直线，但不影响我们解题）

题意就转变为了：选出的瓶盖中距离最近的2个距离为x时，选出的瓶盖数量是否不少于m，其中x要尽可能大；

#include <cstdio>   
#include<algorithm>
int a[100005], n, m;
template<typename T>
inline T max(T x, T y)
{
    return x > y ? x : y;
}
template<typename T>
inline T min(T x, T y)
{
    return x > y ? y : x;
}
bool check(int x)
{
    int now = 1, num = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] - a[now] >= x) /*满足条件则选*/
        {
            now = i;
            num++;
        }
    }
    return num >= m;/*选出瓶盖的数量是否不少于m*/
}
int main()
{
    int L = 1, R = -9999999;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        R = max(R, a[i]);
    }
    std::sort(a + 1, a + 1 + n);/*还有跟我一样漏掉这行的SB吗？*/
    delete t;
    int ans = 0;
    while (R-L>=5)/*答案控制在一个较小的区间内*/
    {
        int mid = L + R >> 1;
        if (check(mid))
        {
            ans = mid;
            L = mid;
        }
        else
            R = mid;
    }
    for (int i = L; i <= R; i++)    /*枚举*/
    {
        if (check(i))
        {
            ans = max(ans, i);
        }
    }
    printf("%d\n", ans);
}

告诉你个奇技淫巧

在其他题解中，很多dalao强调了L和R还有mid的问题，这让许多萌新不知所措，其实这样就好了

把答案控制在一个较小的区间内，最后来枚举

    while (R-L>=5)
    {
        int mid = L + R >> 1;
        if (check(mid))
        {
            ans = mid;
            L = mid;
        }
        else
            R = mid;
    }
    for (int i = L; i <= R; i++)
    {
        if (check(i))
        {
            ans = max(ans, i);
        }
    }

如果你发现本题解有写得不够清楚甚至是错的，请私信给我