技术教程 编程代码 AcWing 4798. 打怪兽题解 正文

AcWing 4798. 打怪兽题解

2023-08-05,,

可以从 \(1\) 枚举到 \(n\) 表示要打多少个怪兽。

因为你要打 \(t\) 个怪兽，并不管顺序，所以我们可以对 \([1, t]\) 这一段进行排序，然后计算 \(a[t], a[t - 2], a[t - 4], \dots\) 即可（因为你要干掉第 \(t\) 个怪兽的时候，必须要使用 \(a[t]\) 的法力值，因为排过序，所以连着 \(t - 1\) 一起干掉就可以了，对于编号小于 \(t\) 的也可以这么干）。

注意每一次都进行快速排序反而会更慢，我们采用插入排序，每次插入新来的数字即可，插入的时间复杂度: \(O(n)\)。

总时间复杂度：\(O(n^2)\)。

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;

int a[N];

bool check(int k) {

    a[0] = -0x3f3f3f3f;

    int p = k;

    while (a[p] < a[p - 1]) {

        swap(a[p], a[p - 1]);

        p--;

    }

    int res = 0;

    for (int i = k; i >= 1; i -= 2) res += a[i];

    if (res <= m) return true;

    else return false;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> a[i];

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

        if (!check(i)) {

            cout << i - 1 << '\n';

            return 0;

        }

    }

    cout << n << '\n';

    return 0;

}

AcWing 4798. 打怪兽题解的相关教程结束。

《AcWing 4798. 打怪兽题解.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!