P8199

一扶苏一 · 2022-03-12 20:25:38 · 题解

E. 游戏

题意：略，详见题面。

关键词：模拟。

参考难度：绿。

解析：依照题意模拟即可。

对于每种武器开一个 use 数组表示他们使用子弹的编号，即可快速判断某种弹药是不是「无用的」；

可以维护一个变量 last 表示目前背包的剩余空间，在捡物资时，先将物资捡起来并更新 last，然后在 \mathrm{last} \lt 0 时，枚举所有的物资，找到最符合要求的并扔掉即可。

设 used(i) 表示 i 是否是「被用到的」弹药，则 i 比 j 「更应该」被扔掉当且仅当 used(i) \lt used(j) 或者 used(i) = used(j) 且 tm(i) \gt tm(j)，其中 tm(i) 表示 i 最后被捡起的时间。

需要注意的是：使用浮点数进行运算可能产生精度误差，因此可以将容量和占用空间都乘 10，这样就可以全部使用整形运算了。

std 的长度为 69 行，2.5k。

(C++)

#include <array>
#include <iostream>
#include <algorithm>

const int maxn = 105;

int n, m, s, t, w1, w2, lst;

std::array<std::array<int, maxn>, maxn> type, a, b, vis;
std::array<int, maxn> tm, arr, cnt;
const std::array<int, 5> dx{0, -1, 1, 0, 0}, dy{0, 0, 0, -1, 1};
const std::array<int, 10> use{0,  14, 14, 14, 14, 15, 15, 15, 16, 16}, level{5, 2, 2, 3, 4, 2, 3, 3, 1, 1};
const std::array<int, 17> weight{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 50, 40, 30, 20, 2, 1, 5};

inline bool used(int x) { return x && ((x <= 13) ? true : (use[w1] == x || use[w2] == x)); }
inline bool cmp(const int x, const int y) { return tm[x] > tm[y]; }

void work(int curx, int cury) {
  vis[curx][cury] = true;
  if (type[curx][cury] == 17) {
    if (cnt[use[w1]] >= a[curx][cury]) {
      cnt[use[w1]] -= a[curx][cury];
      lst += a[curx][cury] * weight[use[w1]];
    } else if (cnt[use[w2]] >= b[curx][cury]) {
      cnt[use[w2]] -= b[curx][cury];
      lst += b[curx][cury] * weight[use[w2]];
    } else {
      std::cout << curx << ' ' << cury << '\n';
      exit(0);
    }
  } else if (type[curx][cury] < 10) {
    if (level[w1] > level[type[curx][cury]]) w1 = type[curx][cury];
    else if (level[w1] < level[type[curx][cury]] && level[w2] > level[type[curx][cury]]) w2 = type[curx][cury];
  } else {
    lst -= a[curx][cury] * weight[type[curx][cury]];
    for (int i = 0; lst < 0; i = 0) {
      for (int p = 10; p < 17; ++p) if (cnt[p]) 
        if ((!cnt[i]) || (used(p) < used(i)) || ((used(p) == used(i)) && (tm[p] > tm[i]))) i = p;
      int tmp = std::min(cnt[i], (-lst) / weight[i] + ((lst % weight[i]) ? 1 : 0));
      lst += tmp * weight[i];
      cnt[i] -= tmp;
    }
    tm[type[curx][cury]] = t;
    cnt[type[curx][cury]] += a[curx][cury];
  }
}

int main() {
  std::cin >> n >> m >> s >> t; lst = s *= 10;
  for (int i = 1; i <= n; ++i) 
    for (int j = 1; j <= m; ++j) {
      std::cin >> type[i][j] >> a[i][j];
      if (type[i][j] == 17) 
        std::cin >> b[i][j];
    }
  tm.fill(998244353); 
  work(1, 1);
  --t;
  for (int op, curx = 1, cury = 1; ~t; --t) {
    std::cin >> op;
    if (vis[curx += dx[op]][cury += dy[op]]) continue;
    work(curx, cury);
  }
  for (int i = 10; i < 17; ++i) arr[i] = i;
  std::sort(arr.begin() + 10, arr.begin() + 17, cmp);
  std::cout << w1 << '\n' << w2  << '\n';
  for (int i = 1; i < 17; ++i) if (cnt[arr[i]] != 0) 
    std::cout << arr[i] << ' ' << cnt[arr[i]] << '\n';
}

题外话：本题构造数据的方法是：随机修改 std 若干处，然后和正确的 std 对拍，拍出一组加一组。