洛谷 P3615

有一個混廁和一個女廁以及 \(2n\) 個男/女士排隊。若女廁為空，則最前面的女士會進入；隊頭的人會進入他能進的廁所（女性優先進女廁。）

每個人需要在廁所待 \(1min\)（切換不算時間）。你可以重排這個隊列，使得這些人能在 \(n\) 的時間內解決完。并且要最小化一個人后移位置的最大值。

\(n \le 10^{18}\)，輸入是將給定 \(n, m, s_i, k_i(i \le m)，\) 隊列為 \(k_i\) 個 \(s_i\) 按順序拼到一起。

先考慮如何判斷一個序列受否合法。首先男士數量要 \(\le n\)。

不難發現，每時每刻廁所都要是滿的。如果出現女廁為空，但沒有女的了就寄了，也就是若出現了沒有女士但有 \(\ge 2\) 個男士就寄了（一個可以進混廁，因為女士優先進女廁所以是對的）。

倒著考慮，若有一個后綴男士數 $\ge $ 女士數 $ + 2$ 就不行了，可以使用數學歸納法，最后肯定會剩兩個男的。對于所有后綴均滿足即可。

再貪心的考慮重排的方案：顯然是男士前移，女士后移，且一定是最后的男士往前移。所以設一個后綴的男士數為女士數 \(+ k\)，則需要最后 \(k - 1\) 個男士需挪到前面去（也就是有女士要從這 \(k - 1\) 個男士前挪到后面）。則答案為 \(\max \{ k\} - 1\)，需對 \(0\) 取 \(\max\)。

要想到序列合法的條件（倒著考慮，剩下來的人少好分析），以及重排隊列的最優策略。又一次沒想到 正難則反。