题目大意

有 $n$ 个工程师，编号 $1$ 到 $n$。
完成一个项目需要至少 $k$ 单位工作量。
如果项目完成，第 $i$ 个工程师获得奖金 $a_i$，但他若完成 $c_i$ 单位工作，则收益为

$$s_i = a_i - c_i \cdot b_i$$

其中 $b_i$ 是他每单位工作的成本。
如果项目未完成，所有人收益为 $0$。
每个工程师依次宣布自己完成的工作量 $c_i$，目标是最大化自己的收益。
若预期收益为负，则选择 $c_i = 0$。
已知所有 $a_i, b_i$，求最终每个工程师宣布的 $c_i$。

关键观察

$1$. 个人最大可接受工作量
对工程师 $i$，若项目完成，则他希望 $s_i \ge 0$，即

$$a_i - c_i b_i \ge 0 \quad\Rightarrow\quad c_i \le \frac{a_i}{b_i} $$

由于 $c_i$ 是整数，定义

$$\text{cap}_i = \left\lfloor \frac{a_i}{b_i} \right\rfloor $$

这是该工程师在不亏损的前提下最多愿意完成的工作量。
如果项目完成，他只会选择 $c_i \in [0, \text{cap}_i]$，且当 $c_i = \text{cap}_i$ 时收益可能为 $0$（题目允许零收益时仍工作）。

$2$. 项目完成条件
设 $S = \sum_{i=1}^n c_i$。

• 若 $S \ge k$，则项目完成，所有人获得奖金，收益为 $a_i - c_i b_i$。
• 若 $S < k$，则项目失败，所有人收益为 $0$。

工程师只有在确信项目最终能完成时才会付出正的工作量，否则不如不工作（收益 $0$）。

$3$. 逆向归纳（从后向前决策）
因为决策顺序固定且信息完全，可以用逆向归纳求解。

• 最后一个工程师（第 $n$ 个）看到前面 $n-1$ 人已经完成了 $S_{n-1}$ 单位。
  若 $S_{n-1} \ge k$，他直接选 $c_n = 0$。
  若 $S_{n-1} < k$，他需要决定是否工作。
  设剩余需要量 $r = k - S_{n-1}$。
  若 $r \le \text{cap}_n$，他选择 $c_n = r$（刚好使项目完成，收益最大）。
  若 $r > \text{cap}_n$，他无法独自补足缺口，且他知晓后面没人了，因此项目必失败，他选 $c_n = 0$。
• 倒数第二个工程师（第 $n-1$ 个）知道第 $n$ 个会如上反应。
  他可以选择自己的 $c_{n-1}$，然后预测第 $n$ 个的响应。
  类似分析可知，每个工程师都会在“自己能补足剩余缺口”时恰好补足，否则贡献自己的全部能力 $\text{cap}_i$，让前面的人继续尝试。
  这等价于 从后向前贪心：维护当前仍需完成的工作量 $\text{rem}$，初始为 $k$。
  对于 $i$ 从 $n$ 到 $1$：
  若 $\text{cap}_i \ge \text{rem}$，则 $c_i = \text{rem}$，$\text{rem} = 0$，结束。
  否则 $c_i = \text{cap}_i$，$\text{rem} \leftarrow \text{rem} - \text{cap}_i$。
• 如果遍历完所有人后 $\text{rem} > 0$，说明所有工程师的总能力 $\sum \text{cap}_i < k$，项目无法完成，此时所有 $c_i$ 都应为 $0$。

算法步骤

$1$. 读入 $n, k$，数组 $a[1..n]$ 和 $b[1..n]$。
$2$. 计算每个工程师的最大可接受工作量：

$$\text{cap}_i = \left\lfloor \frac{a_i}{b_i} \right\rfloor $$

$3$. 初始化 $\text{rem} = k$，数组 $c$ 全为 $0$。
$4$. 从 $i = n$ 递减到 $1$：

• 若 $\text{rem} == 0$，跳出循环。
• 令 $take = \min(\text{cap}_i, \text{rem})$。
• $c_i = take$，$\text{rem} \leftarrow \text{rem} - take$。
  $5$. 若最后 $\text{rem} > 0$，将 $c$ 全部置为 $0$（项目无法完成）。
  $6$. 输出 $c_1, c_2, \dots, c_n$。

复杂度分析

• 计算 $\text{cap}_i$ 需要 $O(n)$。
• 逆向遍历一次 $O(n)$。
• 总时间复杂度 $O(n)$，空间复杂度 $O(n)$。
  满足 $n \le 1000$ 和 $k \le 10^6$ 的限制。

正确性说明

该贪心算法完全模拟了逆向归纳的均衡结果：

• 最后一个工程师会在力所能及的情况下恰好完成剩余工作量，否则放弃。
• 前面的工程师知道后面的人会这样行动，因此他们也会在力所能及时填补缺口，否则贡献全部能力。
• 若总能力不足，所有人都得不到奖金，最优选择是 $c_i = 0$。
• 每个工程师的决策都最大化了自己的收益，且结果唯一。

参考代码（C++）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    vector<int> cap(n);
    for (int i = 0; i < n; ++i) {
        cap[i] = a[i] / b[i];   // 向下取整
    }

    vector<int> c(n, 0);
    int rem = k;

    for (int i = n - 1; i >= 0; --i) {
        if (rem == 0) break;
        int take = min(cap[i], rem);
        c[i] = take;
        rem -= take;
    }

    if (rem > 0) {
        fill(c.begin(), c.end(), 0);
    }

    for (int i = 0; i < n; ++i) {
        cout << c[i] << " \n"[i == n - 1];
    }

    return 0;
}

样例验证

样例1

$n=3, k=6$
$a = [4,7,6],\ b = [1,2,3]$
$\text{cap} = [4,3,2]$
从后向前：

• $i=3$: $take=\min(2,6)=2$, $c_3=2$, $rem=4$
• $i=2$: $take=\min(3,4)=3$, $c_2=3$, $rem=1$
• $i=1$: $take=\min(4,1)=1$, $c_1=1$, $rem=0$
  输出 $1\ 3\ 2$，符合。

样例2

$n=3, k=12$
$\text{cap}=[4,3,2]$，总能力 $9 < 12$
最终 $rem=12-9=3>0$，全部置 $0$，输出 $0\ 0\ 0$。

样例3

$n=3, k=11$
$a = [6,7,8],\ b = [1,2,3]$
$\text{cap}=[6,3,2]$
从后向前：

• $i=3$: $take=\min(2,11)=2$, $c_3=2$, $rem=9$
• $i=2$: $take=\min(3,9)=3$, $c_2=3$, $rem=6$
• $i=1$: $take=\min(6,6)=6$, $c_1=6$, $rem=0$
  输出 $6\ 3\ 2$，符合。

---

总结：本题利用逆向贪心，将多阶段完全信息博弈转化为简单的从后向前填补缺口的过程，时间复杂度 $O(n)$，是典型的最优策略分配问题。**