我是按照 《算法竞赛入门经典训练指南》的思路想的,可是想到一半线索突然断了。
若原数列为 A={15,7,11,3,14},设每个人最后的纸牌数为 M,则 M=8。设 xi 表示 i 给 i−1 的数量。
因为 A1−x1+x2=M,所以有:
x2=x1−(A1−M)=x1−7
同理。有:
x3=x1−6
x4=x1−9
x5=x1−4
显然,当 x1=6 时,是最优解之一。
此时有 x={6,−1,0,−3,2}
于是可以据此填写下张表:
| 下标 | 给 i−1 的牌数 | 给 i+1 的牌数 |
|---|
| 1 | 6 | 1 |
| 2 | −1 | 0 |
| 3 | 0 | 3 |
| 4 | −3 | −2 |
| 5 | 2 | |
可是到这里忽然填不了了。按照 x 来看,5 号应该给 1 号 −6 张牌,可是这里只有填 4 才能保证 5 号最后有 8 张牌。
求大佬解决