https://codeforces.com/contest/1923/problem/B

题意

您正在玩一款电脑游戏。游戏的当前关卡可以用一条直线来模拟。你的角色位于这条直线的 $0$ 点。有 $n$ 个怪物试图杀死你的角色；其中 $i$ 个怪物的健康值等于 $a_i$ ，并且最初位于 $x_i$ 点。

每秒钟都会发生以下情况：

• 首先，你最多向怪物发射 $k$ 颗子弹。每颗子弹的目标正好是一个怪物，并使其生命值减少 $1$ 。对于每颗子弹，你可以任意选择目标(例如，你可以将所有子弹都射向一个怪物，也可以将所有子弹都射向不同的怪物，或者选择任何其他组合)。任何怪物都可以成为子弹的目标，不受其位置和其他因素的影响；
• 然后，所有健康值为 $0$ 或更低的活着的怪物死亡；
• 然后，所有活着的怪物向您移动 $1$ 点(在您左边的怪物坐标增加 $1$ ，在您右边的怪物坐标减少 $1$ )。如果有怪物接近你的角色(移动到 $0$ 点)，你就输了。

你能在杀死所有 $n$ 只怪物的同时，不让任何一只怪物靠近你的角色吗？

题解

我们每秒钟都将 $k$ 发子弹射击最近的若干怪物，模拟过程即可。

#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 300010;
int t, n, k;
struct E {
  int v, p;
} a[maxn];
bool cmp (E x, E y) {
  return x.p < y.p;
}
int main () {
  ios::sync_with_stdio (false);
  cin.tie (0);
  cin >> t;
  while (t--) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i].v;
    for (int i = 1; i <= n; i++) cin >> a[i].p, a[i].p = abs (a[i].p);
    sort (a + 1, a + n + 1, cmp);
    bool flag = true;
    for (int ti = 1, tot = 1; flag && tot <= n && ti <= n; ti++) {
      int x = k;
      while (x > 0 && tot <= n) {
        int tmp = min (a[tot].v, x);
        a[tot].v -= tmp; x-= tmp;
        if (a[tot].v <= 0) tot++;
      }
      if (tot <= n && a[tot].p - ti <= 0) flag = false; 
    }
    cout << (flag ? "YES" : "NO") << '\n';
  }
  return 0;
}