吃鸡背包模拟(Battle Royale Game) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int weapon_prio(int w) {
    if (w == 0) return 0;
    if (w == 4) return 1; // Kar98K
    if (w == 3 || w == 6 || w == 7) return 2; // SKS, MK12, Mini14
    if (w == 1 || w == 2 || w == 5) return 3; // Beryl, AKM, M416
    if (w == 8 || w == 9) return 4; // S686, DBS
    return 0;
}

int weapon_ammo(int w) {
    if (w >= 1 && w <= 4) return 14;
    if (w >= 5 && w <= 7) return 15;
    if (w == 8 || w == 9) return 16;
    return -1;
}

int item_weight10(int id) {
    if (id == 10) return 50;
    if (id == 11) return 40;
    if (id == 12) return 30;
    if (id == 13) return 20;
    if (id == 14) return 2;
    if (id == 15) return 1;
    if (id == 16) return 5;
    return 0;
}

struct Cell {
    int type, y, b;
    bool visited = false;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k, t;
    if (!(cin >> n >> m >> k >> t)) return 0;
    int cap10 = k * 10;
    vector<vector<Cell>> grid(n + 1, vector<Cell>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int x;
            cin >> x;
            if (x == 17) {
                int a, b;
                cin >> a >> b;
                grid[i][j] = {17, a, b, false};
            } else {
                int y;
                cin >> y;
                grid[i][j] = {x, y, 0, false};
            }
        }
    }
    vector<int> ops(t);
    for (int i = 0; i < t; ++i) cin >> ops[i];

    int w1 = 0, w2 = 0;
    vector<long long> cnt(17, 0);
    vector<int> last_time(17, -1);

    auto is_unneeded_bullet = [&](int id) -> bool {
        if (id < 14 || id > 16) return false;
        return weapon_ammo(w1) != id && weapon_ammo(w2) != id;
    };

    auto cur_used10 = [&]() -> long long {
        long long s = 0;
        for (int id = 10; id <= 16; ++id) s += cnt[id] * item_weight10(id);
        return s;
    };

    int r = 1, c = 1;
    auto enter_cell = [&](int step_time) -> bool {
        Cell& cell = grid[r][c];
        if (cell.visited) return true;
        cell.visited = true;
        if (cell.type == 17) {
            int a = cell.y, b = cell.b;
            int am1 = weapon_ammo(w1);
            int am2 = weapon_ammo(w2);
            if (am1 != -1 && cnt[am1] >= a) {
                cnt[am1] -= a;
                return true;
            }
            if (am2 != -1 && cnt[am2] >= b) {
                cnt[am2] -= b;
                return true;
            }
            cout << r << " " << c << "\n";
            return false;
        }
        int x = cell.type, y = cell.y;
        if (x >= 1 && x <= 9) {
            int p = weapon_prio(x);
            int p1 = weapon_prio(w1);
            int p2 = weapon_prio(w2);
            if (p > p1) {
                w1 = x;
            } else if (p < p1 && p > p2) {
                w2 = x;
            }
            return true;
        }
        // Ammo or grenade (10..16)
        long long need10 = 1LL * y * item_weight10(x);
        long long free10 = cap10 - cur_used10();
        if (free10 < need10) {
            long long lack10 = need10 - free10;
            // First drop unneeded bullets ordered by earliest last_time
            while (lack10 > 0) {
                int best = -1;
                for (int id = 14; id <= 16; ++id) {
                    if (cnt[id] > 0 && is_unneeded_bullet(id)) {
                        if (best == -1 || last_time[id] < last_time[best]) best = id;
                    }
                }
                if (best == -1) break;
                int w = item_weight10(best);
                long long drop_cnt = min(cnt[best], (lack10 + w - 1) / w);
                cnt[best] -= drop_cnt;
                lack10 -= drop_cnt * w;
            }
            // Next drop any ammo/grenade ordered by earliest last_time
            while (lack10 > 0) {
                int best = -1;
                for (int id = 10; id <= 16; ++id) {
                    if (cnt[id] > 0) {
                        if (best == -1 || last_time[id] < last_time[best]) best = id;
                    }
                }
                if (best == -1) break;
                int w = item_weight10(best);
                long long drop_cnt = min(cnt[best], (lack10 + w - 1) / w);
                cnt[best] -= drop_cnt;
                lack10 -= drop_cnt * w;
            }
        }
        cnt[x] += y;
        last_time[x] = step_time;
        return true;
    };

    if (!enter_cell(0)) return 0;
    for (int i = 0; i < t; ++i) {
        int op = ops[i];
        if (op == 1) --r;
        else if (op == 2) ++r;
        else if (op == 3) --c;
        else if (op == 4) ++c;
        if (!enter_cell(i + 1)) return 0;
    }

    cout << w1 << "\n" << w2 << "\n";
    vector<int> items;
    for (int id = 10; id <= 16; ++id) {
        if (cnt[id] > 0) items.push_back(id);
    }
    sort(items.begin(), items.end(), [&](int a, int b) {
        return last_time[a] < last_time[b];
    });
    for (int id : items) {
        cout << id << " " << cnt[id] << "\n";
    }
    return 0;
}