题解 P3615 【如厕计划】

kkksc03 · 2017-02-26 23:11:29 · 题解

• ~20分做法：输出-1~出题人下次再也不敢了这么做了。

• 真·20分做法：2^N*N^2的暴力生成每一种队列，然后计算不满意度。然而显然没人这么写。

• 60分做法：

首先我们要判断，怎样的一个序列是可行的。你可以从头开始模拟……可是没必有。题目有一个条件，N分钟，2N个人。那么所有的厕所必须不可以空。那我们可以倒者推。

如果最后面有两个男的，那么最后一分钟你们还是商量一下谁进女厕吧。所以我们可以猜想，男的应该尽可能靠前。而且不能超过N个男的，否则N个混合厕所不够分啊。

还是从后面推。我们把女性设为+1，男性设为-1，然后从队伍末尾开始开始计算后缀和。一但后缀和到了-2，就说明到了两个男的商量谁去女厕的地步。所以说只要保证后缀和一直大于等于-1，那么这个就一定可以在N分钟内解决（请读者自行证明，利用数学归纳法）

               1   2   3   4   5
   F   F   F   M   M   M   M   M   F   F
                   -2  -1  0   1   2   1
                 (gg了)

因此，我们希望每个妹子退后C位，使后缀和一直不小于-1。因此不满的永远是妹子（奸笑）。这个C要尽可能小。

怎么构造这样一个队列呢？很简单，从队伍末尾挑出C（这里为2）个汉子，全部安排在队首。对了，每个M或者每个F都是不区分的。

   1   2               3   4   5
   M   M   F   F   F   M   M   M   F   F
   0  -1   2   1   0  -1   0   1   2   1

我们可以看出，编号相同的男的，不会变的更加前面，而除了后面的女的，都退后了2个位。

于是，我们可以很愉快的二分C。60分

• 100分解法

其实完全没有必要。

我们可以画一个折线图，记录后缀和曲线（请读者自备纸笔），从后往前。我们可以发现，每将一个男的移动到前面去，折线图就会整体往上面移动1。所以说，我们只要计算整个序列中后缀和最小值是多少。每一个小段都可以算出后缀和的贡献，然后我们就O(M+sigma(Si))可以求出这个值，假设是-k。那么最终答案就是k-1。