求助环形均分纸牌问题
  • 板块学术版
  • 楼主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 表示 iii1i - 1 的数量。

因为 A1x1+x2=MA_1 - x_1 + x_2 = M,所以有:

x2=x1(A1M)=x17x_2 = x_1 - (A_1 - M) = x_1 - 7

同理。有:

x3=x16x_3 = x_1 - 6 x4=x19x_4 = x_1 - 9 x5=x14x_5 = x_1 - 4

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

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

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

下标i1i - 1 的牌数i+1i + 1 的牌数
116611
221-100
330033
443-32-2
5522

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

求大佬解决

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