求助环形均分纸牌问题
  • 板块学术版
  • 楼主Micnation_AFO
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/4/28 14:12
  • 上次更新2023/10/28 02:44:36
查看原帖
求助环形均分纸牌问题
574944
Micnation_AFO楼主2022/4/28 14:12

我是按照 《算法竞赛入门经典训练指南》的思路想的,可是想到一半线索突然断了。

若原数列为 A={15,7,11,3,14}A = \lbrace15, 7, 11, 3, 14\rbrace,设每个人最后的纸牌数为 MM,则 M=8M = 8。设 xix_i 表示 ii 给 i−1i - 1 的数量。

因为 A1−x1+x2=MA_1 - x_1 + x_2 = M,所以有:

x2=x1−(A1−M)=x1−7x_2 = x_1 - (A_1 - M) = x_1 - 7

同理。有:

x3=x1−6x_3 = x_1 - 6 x4=x1−9x_4 = x_1 - 9 x5=x1−4x_5 = x_1 - 4

显然,当 x1=6x_1 = 6 时,是最优解之一。

此时有 x={6,−1,0,−3,2}x = \lbrace6, -1, 0, -3, 2\rbrace

于是可以据此填写下张表:

下标给 i−1i - 1 的牌数给 i+1i + 1 的牌数
116611
22−1-100
330033
44−3-3−2-2
5522

可是到这里忽然填不了了。按照 xx 来看,55 号应该给 11 号 −6-6 张牌,可是这里只有填 44 才能保证 55 号最后有 88 张牌。

求大佬解决

2022/4/28 14:12
加载中...