这是一个 interactive page描述问题和 academic paper复习数学。
问题大致可以描述如下。
给定一个任意长度的 bool 值数组,表示 n
个相邻的小便池,true
的值表示已占用, 的值false
表示空,在给定任何配置的情况下,您将如何构建算法来填充此数组,同时:
通过让一个人尽可能远离两侧的其他小便器,最大限度地保护每个人的“隐私”。
通过确保配置在最后可能的时间饱和来尽可能长时间地维护此隐私。
面对多个次优选择,优先考虑两边没有相邻小便池的小便池,而不是仅空置的相邻小便池。
为了简单起见,我标记了这个 javascript,但任何代码或伪代码都可以。
var urinals = Array
.apply(null, new Array(n))
.map(Boolean.prototype.valueOf,false);
编辑 - 在这里发现一个相关问题:
最佳答案
尽可能接近解决方案:
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]
并不总能产生最佳结果(有时不同的放置可能会导致稍后移动几步就饱和)并且不喜欢末端小便器,但在分散值并尽可能长时间地保持最小缓冲方面做得很好.
关于javascript - 最佳小便池策略,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21210997/