kuro 在学习操作系统的时候接触到了著名的银行家算法。
对于一般的情况,可以使用课本上给出的算法进行安全性检查,但她认为这种做法太暴力了!她想知道:在一些特殊情形下,是否存在时间复杂度更优的算法?
具体地,kuro 只关心 资源种类数 (m = 2) 的情形。
形式化的说,现在有 两种不同的资源,你一开始分别拥有 个单位。
共有 个人在等待你提供资源。
对第 个人,有四个参数:
- :他需要的第 1 种资源数量
- :他需要的第 2 种资源数量
- :如果你满足他的需求,他额外返还的第 1 种资源数量
- :如果你满足他的需求,他额外返还的第 2 种资源数量
一次“操作”定义如下:
- 当前你拥有的两种资源为 。
- 若
则你可以对第 个人进行一次操作:
因此操作结束后,你拥有的资源变为:
你对 每个人最多只能进行一次操作,并且希望最终对 所有 个人都进行一次操作。
你的任务是判断是否存在一种顺序,使得:
- 在每一步操作时,你拥有的两种资源均保持非负;
- 最终每个人都恰好被操作一次。
若存在任意一种合法顺序,请输出YES和操作顺序;否则请输出 NO。