一道关于匹配的题目，99%的人都会答错_【Gad腾讯游戏开发者平台】

千人策划群里激烈讨论了近半小时，居然都没有人写出正确答案。...

之前在某千人策划群里看见一道题目，大意是这样的：

一个由X人参加的游戏，假定每一局对局时间是Y，需要保证玩家平均匹配时间为T秒，且上一局一起对局过的玩家t秒内不会匹配到一起。

问，至少需要多少玩家才能保证达成条件？

不要着急去评论区留言，这样的题目还需要特地写一篇？

事实是，群里激烈讨论了近半小时，居然都没有人写出正确答案。

第二天进群一看，大家终于统一意见得出了一个错误答案……

言归正传，大家可以尝试自己解答一遍，得出一个答案后再来看解答过程。

由于本人比较傲娇，所以喜欢直接给出结果：XY/T。但是没关系，现在收手，不要向下滑动屏幕，你依然有机会得出答案的计算过程。因为答案是错的。

皮这一下我很开心。

首先，玩家平均匹配时间为T秒，可以简单理解为，平均T秒，游戏新开一个房间。每一局对局时间是Y，所以，一共需要Y/T个房间。每个房间里有X人，所以一共需要XY/T名玩家。

一部分得出XY/T的朋友们倒在这里。

但是！如果只有XY/T名玩家，玩家完全可以直接开始下一把，但玩家平均匹配时间为T，所以，我们至少还需要X名玩家，所以，需要XY/T+X名玩家。

一部分得出XY/T+X的朋友们倒在这里。

但是！题目还有一个条件，上一局一起对局过的玩家t秒内不会匹配到一起。所以，游戏每新开一局，就需要来自原先X个房间的玩家。所以，t秒内不能匹配到一起的条件中，t对结果没有影响。

一部分得出XXY/T的朋友们倒在这里。

但是！如果真有这么多人，Y个房间就不够玩家进入了。这是因为部分朋友没有考虑到匹配的方式。我们考虑最优的方式。

我们将房间里的玩家编号为1~x，房间编号为A~Y，这时我们就得到一个关于玩家编号的数组。类似于这样：

我们随意选择一组刚出游戏的玩家，假定为第m组，为了让第m组的玩家平均T秒进入游戏，采取最直观的线性方法，我们需要让第m组的玩家在2T的时间内全部进入游戏，平均每2T/（X-1）秒有一人进入游戏，即，我们让编号为mx的玩家直接匹配进入游戏，编号m(x-1)的玩家在2T/(X-1)秒后匹配进入游戏，直到2T秒后，玩家m1进入游戏。我们发现，只要每组都采取同样的策略，就不会产生额外的玩家交叉。类似于这样：

所以，在这一段时间里不在游戏中的玩家就需要额外算上。

显然、易得，这一部分的玩家共XX/2-X/2人。

加上游戏房间内的玩家，一共XY/T+XX/2-X/2人

一部分得出XY/T+XX/2-X/2的朋友们倒在这里。（好吧，其实连走到这里的朋友都没有。可能真正的大佬们都不屑于出手吧。)

但是！玩家进入游戏的时间间隔不再是T秒，也就是说，由于平均每2T/（X-1）秒有一人进入游戏，我们也要每2T/（X-1）秒开一个房间。由于，一局游戏的时间为Y，所以，我们需要Y(X-1)/2T个房间，所以，一共需要Y(X-1)X/2T+XX/2-X/2名玩家

一部分得出Y(X-1)X/2T+XX/2-X/2的朋友们倒在这里。（我相信会有的，LOL……)

但是！在题目中，我们并没有X和Y大小关系的前提。其实到这里就有点抠字眼了，但是，为了尽可能地解决一个问题，作为游戏策划一定要面面俱到……

为了在每次匹配时都能凑足X人，我们需要至少X个房间，所以，当X>Y(X-1)/2T，即Y=2TX/(X-1)，且Y+T>t>T！

OK，到现在为止，经过我们严密的思考和计算，完美得出了题目缺失的四个限制条件，让我们再来算一算。

让我们再回头想一想，如果对局时间Y和房间数量没有关系，为什么我们会认为他们有关系？

因为我们之前没有玩家必须完成一局就立即进入匹配且所有玩家只在内部循环这样的限制，所以才让X这样的答案有机可乘。现在我们加上限制，发现答案回归到需要Y(X-1)/2T个房间，房间内共Y(X-1)X/2T名玩家。

假定，我们有一种最优的算法，所有房间内的玩家一结束游戏就能立即完成匹配，那房间外的玩家数量m就满足（Y(X-1)X/2T+m）=mY，得出房间外的玩家最低极限数量为Y(X-1)X/2（Y-T），所以，我们至少需要Y(X-1)X/2T+Y(X-1)X/2（Y-T）名玩家。

即，YY(X-1)/2T(Y-T)名玩家。

一部分得出YY(X-1)/2T(Y-T)的朋友们倒在这里。

但是！这样的匹配方式我们能不能找到呢？这就要看t和T之间的关系了。假定我们有Y+T>t>T的限制条件，那么，Y(X-1)X/2T+XX/2-X/2的确是正确答案。但，只要t由2T向0慢慢逼近，答案也会由Y(X-1)X/2T+XX/2-X/2向YY(X-1)/2T(Y-T)减小。只要t由Y+T向正无穷增长，答案也会由Y(X-1)X/2T+XX/2-X/2逐渐向正无穷增长。

所以，所需要的玩家总数其实是关于t的函数！而且至少分三段的正相关函数。所以，之前关于t对结果没有影响的论断也是错的！

但是！作为一个专业的策划，不得出t和玩家总人数的直接关系前是不会撒手的！

我们已经知道，在t∈（T,Y+T]时，至少需要Y(X-1)X/2T+XX/2-X/2名玩家。

在t∈[0,T]时，要得到YY(X-1)/2T(Y-T)的最小结果，需要满足Y(X-1)X/2（Y-T）大于X，得到X>3-2Y/T，由于，我们有条件，Y>=2TX/(X-1)，所以，X>3-4X(X-1)，由于X是整数，所以只需要X>1就足够了……

好像是废话，所以，我们加上X>1,Y>1的条件……

一部分得出YY(X-1)/2T(Y-T)的朋友们倒在这里。

但是！我们YY(X-1)/2T(Y-T)是t=0的情况下，考虑t之后，需要满足条件，（Y(X-1)X/2T+m）=mY+Y(X-1)X/2Tt，解得，m=YX(X-1)(T-t)/2T(Y-T)，所以，在t∈[0,T]时，至少需要Y(X-1)X/2T+YX(X-1)(T-t)/2T(Y-T)名玩家。

在t∈[Y+T,∞）时，我们发现，这个条件可以简单理解为，某一局对局过的玩家后面的多局游戏都不能匹配到一起。当然，这个理解不准确，但可以帮助我们理解这个时间的意义。但是，我们得出了这个结论的意义在哪里呢？因为，得出这个结论折后，我们就可以快速地利用之前的结果。但，直接靠时间的数值叠加玩家数量肯定是不对的。但，结果好像确实是这样……我们令玩家不能匹配到一起的局数为n，n=[(t-T)/(T+Y)]+1。n每加一，便进行一次循环，并额外增加XX/2-X/2名玩家。所以，至少需要玩家的总人数为：

t∈[nY+nT,nY+(n+1)T] (n>=1)时，至少需要Y(X-1)X/2T+YX(X-1)((n+1)T+nY-t)/2T(Y-T)+([(t-T)/Y])(XX/2-X/2)名玩家

t∈[nY+(n+1)T,(n+1)Y+(n+1)T] (n>=1)时，至少需要Y(X-1)X/2T+([(t-T)/Y]+1)(XX/2-X/2)名玩家

所以，我们总结一下，作为一个策划，一定要能扯，会扯，扯得有逼格（划掉）。

t∈[nY+nT,nY+(n+1)T] (n>=0)时，至少需要Y(X-1)X/2T+YX(X-1)((n+1)T+nY-t)/2T(Y-T)名玩家

t∈[nY+(n+1)T,(n+1)Y+(n+1)T] (n>=0)时，至少需要Y(X-1)X/2T+([(t-T)/Y]+1)(XX/2-X/2)名玩家

在坐标轴上表示，大概是这样的：

一部分得出以上结论的朋友们倒在这里……

在这里还需要再验证前提，那就是t的上限。

此处略去不知道多少字……

发现t的上限没有要求……

一部分得出以上结论的朋友们倒在这里……

但是！玩家总数一定是整数啊，所以连续的函数一定是不对的。所以，我们需要将结果取整。直接加上中括号进行取整加一吗？

算了，太难掰了……答案是如果强制精确的话，结果是我们所得曲线上所有与整数t互素的整数点，与分数非整数t分子互素，并且值为t分母倍数的整数点的集合解……

所以，结果大概是这样的……（红色为解）。

别问我为什么是这样，我也阵亡了，就倒在这里了……

如果只想得出个大概结果，直接取整加一也可以……

当然，这是在限制了诸多条件的前提下。如果限制了t的范围，玩家总数一样可以表示为X的函数，Y的函数，T的函数。以上大概是我探索了该问题二十分之一的内容的总结……

这就是数学的魅力啊！

当然，在实际工作中，我们并不会也不需要这么做……所以，这只是一道简单的数学问题。但却引起了我深刻的思考，为什么简单的条件总是导致复杂结果？所以，宇宙也许并不懂数学。最经典的就是三体问题，简单的相互吸引的3个质点，居然得不出解析解…… 我好像又发现了一个比肩P=NP的难题。

但是！明明是很严肃的数学问题，总有人问我一些奇奇怪怪的问题，比如说：