题意

构造一个非空括号字符串,要求正好包含k个合法括号对
字符串长度不能超过十万

*

思路

看到这个k的数据范围和字符串长度要求,我们知道不能一个劲怼括号,否则会超出长度限制

那么我们先来思考一个问题:
一个长度为n的字符串,如何出现最多的括号对?(为了方便描述,我假定n为偶数)
答案是把字符串一分为二,左边全是左括号,右边全是右括号,这样我们就得到了个括号对。

把上面这个过程反过来,我们需要正好个合法括号对,那么我们先令,字符串左边放入个左括号,右边放入个右括号,那么我们就得到了个括号对。
因为是向下取整的,所以我们可能会漏掉一些括号对,这时候需要把漏掉的括号对补上

我们需要补上个括号对,因为字符串右边有个右括号,所以我们每在字符串左边加一个左括号就会增加个括号对
在字符串左边加上个括号对以后,我们还需要补上个括号对。这时候不能再去字符串左边加左括号,因为这么做得到的括号对会大于。这样,我们就要从字符串的右边入手。

字符串右边现在是右括号,我们需要补上的括号对又小于,所以我们可以从右往左数个位置,从那里插入一个左括号,这样整个字符串就增加了个右括号,得到了刚好个合法括号对。

例子,先生成字符串 (()),再从字符串左边补上个括号对,变成((()),还差一个括号对,从字符串从右往左数第个位置插入左括号,得到((()(),正好7个合法括号对

代码

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int k;
    cin >> k;
    //如果k=0则输出包含0个合法括号对的非空括号字符串
    if (k == 0) {
        cout << ")";
        return 0;
    }
    //k开根号先生成一些括号对
    int t = (int) sqrt(k);
    //实际需要的括号对和当前括号对数量的差值
    int delta = k - t * t;
    //在最左边每添加一个"("就会多出t对合法括号对
    for (int i = 0; i < delta / t; ++i) {
        cout << "(";
    }
    //原有的t个"("
    for (int i = 0; i < t; ++i) {
        cout << "(";
    }
    //加了整数倍t个括号对以后还差delta个括号对
    delta = delta % t;
    //先输出原有的t个")"
    //从右往左数,差几个括号对就从第几个位置插入一个"("
    //如果不差括号对就不再插入(这里放在了最后一个)
    for (int i = 0; i < t + 1; ++i) {
        if (i == (t - delta))cout << "(";
        else cout << ")";
    }
}