题目重点:明确允许找零与回收,再用二进制子集表示证明两次切割足够且必要。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练金条均匀可按长度切,两次切成三段;每天工人累计持有当天数份额,允许归还已收段并交换。
- 如果不允许找零/回收,1/2/4方案不满足每日新增一份,必须另判。
解题路线
- 把整条按七天工资归一化为7单位,切在1和3位置,得到1、2、4三段。两次切割不是每天都切,而是预先获得可反复交换的三段。
- 第d天工人累计应持有d单位,用d的三位二进制选择段,1至7都可表示。雇主与工人交换整段,净增加工资1单位而不需要当天交一段恰长1。
- 逐日:第1天给1;第2天收1给2;第3天给1;第4天收1和2给4;第5天给1;第6天收1给2;第7天给1。任何一天工人累计持有值都等于天数。
- 正确性是三个权重1/2/4的子集和覆盖0至7,且每次交换把昨日子集改为今日子集,总值差1。工作不可对半继续掰等额外操作不能偷偷加入。
- 必要性:一次切割仅两段,最多2²=4种持有子集,包括0,不能覆盖8种累计金额0至7;至少三段即至少两切。这个下界依赖整段持有、不再切与允许回收的合同。
- 推广2^m−1天可用m段1/2/4…,m−1次切;不是所有任意天数都机械复制同样尾段而不验证覆盖,需先构造连续可表示区间。
手动走一遍
第4天工人原持1和2,雇主把它们收回换给4,净收益1,累计4。若要求每天只能单向交金条不能收回,那么这一步非法,题目应先问清是否可找零。
规模与取舍
固定七天是常量操作;推广m段可表示2^m种子集,日结方案用O(m)位选择,枚举所有天数输出需相应输出规模。
易错点与追问
容易失分的边界
- 省略允许找零前提。
- 第4天直接给4导致累计7。
- 一次切割下界未算可用子集数。
继续深挖
- 不允许归还能否两切完成?
- 任意D天如何构造?
- 重量误差怎样影响实际付款?
