按题意从 f₁ 到 fₙ 依次处理:对每个前端的偏好列表,从高到低找第一个尚未被占用的后端并占用之;若整份清单都被占了,则无法全匹配。
这就是对题目给定贪心过程的直接模拟,无需额外的稳定性或最大匹配算法。
实现要点:
n+1 的布尔数组 used 标记后端是否已被占用。i 个前端的 k 个候选后端按序检查,遇到未占用则标记并继续处理下一个前端;若都占用则直接判定本组数据为 NO(但仍需把输入读完)。∑k < 1e6,顺序扫描即可。现有 n 个前端工程师 f1,f2,f3,...,fn 和 n 个后端工程师 b1,b2,...,bn .
每个前端工程师都有一份想要合作的后端工程师清单,清单按照想要合作的优先级从高到低给出,并且每位后端工程师只能与一位前端工程师合作.
多多在构思合作方案,打算依次处理 ,,九,..,,前端的合作清单,并且对于每个清单按优先级从高到低寻找可合作的后端,如果找到的后端还没有合作对象,那么他们将达成合作关系.请问如果按照上述方案,使得每位前端工程师都能成功匹配到后端工程师的话,输出"YES”,否则输出"NO"(均不包含双引号)