CF1870D Prefix Purchase

你有一个大小为 $n$ 的数组 $a$，初始时所有元素都为零（$a_1 = a_2 = \ldots = a_n = 0$）。你还有一个大小为 $n$ 的整数数组 $c$。 最初，你有 $k$ 个硬币。每当你支付 $c_i$ 个硬币时，你可以将数组 $a$ 的前 $i$ 个元素全部加 $1$（即对所有 $1 \leq j \leq i$，执行 $a_j \mathrel{+}= 1$）。你可以任意多次购买任意 $c_i$。只有当 $k \geq c_i$ 时才能进行购买，也就是说，任何时刻都必须满足 $k \geq 0$。 请你求出能够获得的字典序最大的数组 $a$。 对于长度相同的两个数组 $a$ 和 $b$，如果在第一个不同的位置，$a$ 中的元素小于 $b$ 中对应的元素，则称数组 $a$ 的字典序小于数组 $b$。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示数组 $a$ 和 $c$ 的大小。 每个测试用例的第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq 10^9$），表示数组 $c$。 每个测试用例的第三行包含一个整数 $k$（$1 \leq k \leq 10^9$），表示你拥有的硬币数。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示能够获得的字典序最大的数组 $a$。

在第一个测试用例中，$a_1$ 不能大于 $5$，如果我们购买 $c_1$ 五次，钱就用完了，所以 $a = [5, 0, 0]$。 在第二个测试用例中，$a_1$ 不能大于 $2$，但我们可以各购买一次 $c_1$ 和 $c_2$（无法购买 $c_2$ 两次），所以 $a = [2, 1]$。 由 ChatGPT 4.1 翻译