最优小便池策略

Question

这是一个描述问题的互动页面和一本关于数学的学术论文.

该问题可以粗略地描述如下.

给定表示n相邻小便池的任意长度的布尔值数组,其中true指示占用的值和false指示空闲的值,在给定任何配置的情况下,如何构造用于填充此数组的算法:

• 通过尽可能远离其他任何一侧的排水器来最大化每个乘客的"隐私".

• 通过确保配置在最后可能的时间变得饱和,尽可能长时间地保持这种隐私.

• 面对多个次优选择,优先排尿小便器,两侧没有相邻的小便池,而不是仅仅是未占用的相邻小便池.

我为了简单起见标记了这个javascript,但任何代码或伪代码都没问题.

var urinals = Array
    .apply(null, new Array(n))
    .map(Boolean.prototype.valueOf,false);

---

编辑 - 在这里找到一个相关的问题:

最优座位排列算法

Answer 1

我已经接近解决方案了：

var urinalFinder = function(urinals){
    var gaps = new Array(), last = null;
    for(var i = 0; i < urinals.length; i++){
        last = gaps.length ? gaps[gaps.length - 1] : 0;
        if(last < 0 && !urinals[i] || last > 0 && !!urinals[i] || last == 0) 
            gaps.push(0); // push if new sequence of vacant or occupied
        // negatives are occupied count & positives vacant count
        gaps[gaps.length - 1] += !!urinals[i] ? -1 : 1; 
    }

    // find the first index of the largest gap
    var maxGapSize = Math.max.apply(Math, gaps),
        maxGapGapsIdx = gaps.indexOf(maxGapSize),
        isFirst = maxGapGapsIdx === 0,
        isLast = maxGapGapsIdx === gaps.length - 1,
        maxGapIdx = 0;

    if(maxGapSize < 1) return false; // no gaps available

    var gapPoint = maxGapSize > 3 
            ? Math.ceil(maxGapSize / 3) // per xkcd suggestion
            : isFirst && maxGapSize === 2
                ? 1
                : isLast && maxGapSize === 2 ? 2 : Math.ceil(maxGapSize / 2);

    // find where our chosen gap begins in input array
    for(var i = 0; i < maxGapGapsIdx; i++)
        maxGapIdx += Math.abs(gaps[i]);

    var result = maxGapIdx + gapPoint - 1; // arrays are zero-indexed

    return result;
};

例如，应用于填充 9 个空位的数组将像这样填充它们：

var foo = [0,0,0,0,0,0,0,0,0]; // nine values
for(var i = 0; i < foo.length; i++)
    foo[urinalFinder(foo)] = i+1;

[4, 6, 1, 7, 2, 8, 3, 9, 5]

并不总是产生最佳结果（有时不同的放置可能会在几次移动后出现饱和）并且不利于末端小便池，但在扇动值并尽可能长时间地保持最小缓冲区方面做得相当好。