Solution -「营业」「CF567D」One-Dimensional Battle Ships

题目大意 - 翻译

Alice 和 Bob喜欢在 \(1\times n\) 的表格中玩战舰游戏。游戏开始时，Alice 有 \(k\) 艘战舰，每艘战舰长度为 \(a\)，她需要把这些战舰不重叠且不相邻地放在格子中（不允许有两艘战舰的格子存在公共边）。但她并不会告诉 Bob 她放的位置。

接下来，Bob 会用 \(m\) 颗炮弹尝试打中 Alice 的战舰，每颗炮弹会选择一个格子打击。但由于 Alice 喜欢作弊，所以她不会告诉 Bob 什么时候击中了战舰。请你帮助 Bob 判断，在第几次发射炮弹后，Alice 一定会有一艘战舰被击中。

分析

不难看出整个问题是具有单调性的，即炮弹打出的越多就越有可能达成“战舰肯定被打到了”这一成就。那么就直接考虑 二分答案。

当我们枚举到一个 \(mid\) 的时候，我们将所有在 \(mid\) 之前发射的炮弹对应到原表格上。得到的效果即原表格被分成了很多个区间。

在这样的情况下如果我们考虑每一个区间的左端都被战舰占据（或不被占），且右端一定不被占据。则这样的放置方法一定是合法的，且对于每一个区间，最多可以放 \(\frac{r - l}{a + 1}\) 艘战舰。

那么就可以求到在 \(mid\) 之前的所有炮弹打出的情况下，最多能保证多少战舰不被打到。显然如果这个个数小于 \(k\) ，这个答案就一定可以为最后答案。

当然因为我们要找的是最小的，所以在这个时候就继续往小的找咯。

#include <cstdio>

#include <algorithm>

using namespace std; 

int Max(int x, int y) {return x > y ? x : y;}

int Min(int x, int y) {return x < y ? x : y;}

int Abs(int x) {return x < 0 ? -x : x;}

#include <cstdio>

#include <algorithm>

using namespace std; 

int Max(int x, int y) {return x > y ? x : y;}

int Min(int x, int y) {return x < y ? x : y;}

int Abs(int x) {return x < 0 ? -x : x;}

int read() {

    int k = 1, x = 0;

    char s = getchar();

    while (s < '0' || s > '9') {

        if (s == '-')

            k = -1;

        s = getchar();

    }

    while (s >= '0' && s <= '9') {

        x = (x << 3) + (x << 1) + s - '0';

        s = getchar();

    }

    return x * k;

}

void write(int x) {

    if(x < 0) {

        putchar('-');

        x = -x;

    }

    if(x > 9)

        write(x / 10);

    putchar(x % 10 + '0');

}

void print(int x, char s) {

    write(x);

    putchar(s);

}

const int MAXN = 2e5 + 5;

struct node {

    int id, val;

    node() {}

    node(int Id, int Val) {

        id = Id;

        val = Val;

    }

} q[MAXN];

bool cmp(node x, node y) {

    return x.val < y.val;

}

int n, k, a, m;

bool check(int mid) {

    int ans = 0, last = 0;

    for(int i = 1; i <= m; i++)

        if(q[i].id <= mid) {

            ans += ((q[i].val - last) / (a + 1));

            last = q[i].val;

        }

    ans += ((n - last + 1) / (a + 1));

    return ans < k;

}

int main() {

    n = read(), k = read(), a = read(), m = read();

    for(int i = 1; i <= m; i++) {

        q[i].val = read();

        q[i].id = i;

    }

    sort(q + 1, q + m + 1, cmp);

    int l = 1, r = m, res = -1;

    while(l <= r) {

        int mid = (l + r) >> 1;

        if(check(mid)) {

            res = mid;

            r = mid - 1;

        }

        else

            l = mid + 1;

    }

    print(res, '\n');

    return 0;

}

巴特西

Solution -「营业」「CF567D」One-Dimensional Battle Ships

题目大意 - 翻译

分析

最新文章

热门文章