根据它的声音,这与国际小便器协议选择(ICUP)几乎完全相同,Randall Munroe写了一个很好的分析,包括封闭形式方程和最佳小便器数量图.在阅读本答复的其余部分之前,您应该阅读他的文章.
兰德尔在帖子中提到:
[I]如果你进入一个连续排空笨拙的小便池的浴室,而不是拿一个最后的小便池,你可以走三分之一的路线.这会将尴尬的行分成两个最佳行,将最坏情况转变为最佳情况.
虽然他没有详细介绍,但它暗示了我们正在努力做的事情.如果我们有一个笨拙的小便池(或大便,在我们的情况下),我们可以尝试让第一个人坐在座位上,这样他们就会成为两个不同的最佳小组的结尾.
对于7个席位,基本选择行为可以解决这个问题:
1 _ _ 3 _ _ 2
离开四个空置座位.但是,如果我们将第一个人安排在第三位,我们会得到最佳的3个和5个子组,将我们可能的占用者增加一个.
3 _ 1 _ 4 _ 2
对于25,基本行为同样是次优的,导致在尴尬之前占据了9/25 :
1 _ _ 6 _ _ 4 _ _ 7 _ _ 3 _ _ 8 _ _ 5 _ _ 9 _ _ 2
但是我们可以让位于第9位的人,创建最佳的9 17个子组,如下所示:
3 _ 8 _ 5 _ 9 _ 1 _ 10 _ 6 _ 11 _ 4 _ 12 _ 7 _ 13 _ 2
达到最佳13/25的入住率.
更一般地说,我认为找到比座位数小的最大最佳数字,并且在那里安置第一个人(在25个案例中,17个,相当于从另一个方向的第9个)将始终最大化可占用椅子的数量.在最坏的情况下,如25,这相当于ceil(n/3)Randall提到的情况.
在平均情况下(使用基本座位行为既不是最好的也不是最差的),我们不能总是仅通过安置第一个人来达到50%的占用率,因为我们只能创建一个最佳子组,而另一个不是最佳的.因此,我们采用最大的最优子群,以最小化次优座位的数量.例如,对于20个座位,我们需要17个并创建一个17 4组,这样可以优化尽可能多的座位,只留下两个空座位:
2 _ 7 _ 4 _ 8 _ 3 _ 9 _ 5 _ 10 _ 1 _ _ 6
实际上,这四个组在技术上既是最好的也是最差的,但希望你能看到这种模式如何扩展.