ACM模版

描述

题解

好长时间没有见过51更新4级以下的题了，今天多了一道从CF上抓来的题，很有趣，区间问题，对于我这种做题少的人来说是一种区间新题型。

比较简单的是直接上STL的set，用二分搞搞（代码One）。但是这个耗时贼高，于是发现这道题不用set和二分也是完全可以的（代码Two），利用一维数组从某一出发点向两边查找，其实问题的关键是如何求一段区间能放下多少艘战舰，很明显：

num = (len + 1) / (a + 1);

这样也就没啥问题了。

代码

One：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

const int MAXN = 2e5 + 10;

set<int> s;
set<int>::iterator it;
set<int>::iterator it_;

int vis[MAXN];

int main(int argc, const char * argv[])
{
    int n, k, a;
    cin >> n >> k >> a;

    int m;
    cin >> m;

    int maxNum = (n + 1) / (a + 1); // 初始化最多可以放maxNum艘
    s.insert(0);        // 下界
    s.insert(n + 1);    // 上界
    mem(vis, 0);

    int point;
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &point);
        if (vis[point])
        {
            continue;
        }
        vis[point] = 1;
        s.insert(point);
        it = s.lower_bound(point);
        it--;
        it_ = s.upper_bound(point);
        maxNum -= ((*it_) - (*it)) / (a + 1) - ((*it_) - point) / (a + 1) - (point - (*it)) / (a + 1);
        if (maxNum < k)
        {
            printf("%d\n", i + 1);
            return 0;
        }
    }

    printf("-1\n");
    return 0;
}

Two：

#include <stdio.h>

const int MAXN = 2e5 + 10;

int place[MAXN];

int main()
{
    int n, k, a;
    scanf("%d%d%d", &n, &k, &a);

    int m;
    scanf("%d", &m);

    int flag = -1;
    int left, right;
    int maxNum = (n + 1) / (a + 1);

    int x;
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &x);
        place[x] = 1;
        for (left = x - 1; left >= 1 && place[left] == 0; left--) ;
        for (right = x + 1; right <= n && place[right] == 0; right++) ;
        maxNum -= (right - left) / (a + 1) - (right - x) / (a + 1) - (x - left) / (a + 1);

        if (maxNum < k && flag == -1)
        {
            flag = i + 1;
            break;
        }
    }

    printf("%d\n", flag);
    return 0;
}