Educational Codeforces Round 114 ABCD 题解 (Java/C++)

A. Regular Bracket Sequences

以n=5为例，我们可以立刻写出1种解法：()()()()()。

接着我们可以写出下面4种解法：
(())()()()()
()(())()()()
()()(())()()
()()()()(())

Java

C++

显然，我们是可以找出m的最大最小值的。而且我们可以通过调换顺序来获得最大最小的值之间的任意的m。

考虑m的最大值：不难发现我们按aaaabbbbcccc这样排列时m最大。因此m的最大值为a-1+b-1+c-1。

接着考虑m的最小值：这里不妨假设a的数目最多。那么也不难发现，按ababacacaaaa这样排列时m最小，于是m的最小值为a-b-c-1。

java

C++

我们发现，不论是攻击或是防御，两种行动都是靠勇士的力量来完成的。

因此不难想到，最优解应当尽可能避免防御力量或者攻击力量溢出。比如攻击力量溢出太多的时候，相应的就可能需要花更多金币来补充防御力量。

于是我们只需要根据x，找到力量最接近x的两个勇士分别计算相应的开销去最小值即可。

Java

C++

因为m最多只有$10^5$，因此直接暴力枚举前$10^5$种可能即可。

我们用一个优先队列来对维护各种可能，把力量最高的排在前面。我们首先将最大的可能加入队列。然后如果队首的结果被ban了，就把这个结果相应的n种较小的结果加入队列。

这样最多ban$10^5$次就能得到答案。

Java

C++