括号(构造）

链接：https://ac.nowcoder.com/acm/contest/9981/B
来源：牛客网

请你构造一个非空的括号字符串，包含正好 k 个不同合法括号对。

所谓括号字符串，是指由'('和')'这两种字符构成的字符串。

要求构造的字符串长度不超过100000 。

输入描述:

一个整数 kkk。

0≤k≤1e9

输出描述:

一个仅包含左右括号字符串，其中有 k 个合法的括号对。如果有多种构造方法，输出任意一种合法方案即可。

示例1

输入

复制 3

3

输出

复制 ()()

()()

说明

假设字符串数组下标从 1 开始，则 (1,2), (1,4), (3,4) 共计 3 个合法括号对

当然，"()))" 也是一种合法的构造

示例2

输入

复制 4

4

输出

复制 (())

(())

说明

假设字符串数组下标从 1 开始，则 (1,3), (1,4), (2,3), (2,4) 共计 4 个合法括号对

另外，合法的构造还有"())()"、"()(()(" 等等。。

示例3

输入

复制

9

输出

复制 

()))))))))

说明

合法的还可以是：

())())()

((()))

)()()())(

等等等。。有非常多种合法构造，输出任意即可。

 

 

做这个题的时候先考虑一下，如果让你构造一个10个合法括号用长度为7的字符串，的话你怎么构造？

2*5是一个很好的选择，( ( ) ) ) ) )但是如果构造11个合法括号的，那就是再最右边的括号在给他加一个( ( ) ) ) ) ( ),

按照这样一个思路验证一下

1e9/35000==28571   1e9%35000假设最大时35000,两个相加不超过100000,所以可行

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
const int mod=998244353;
int main(){
    int k;
    cin>>k;
    if(k+1<=100000){
        printf("(");
        for(int i=1;i<=k;i++){
            printf(")");
        }
    } 
    else{
        //50000
        int p=k/35000;
        int z=k%35000;
        for(int i=1;i<=35000;i++){
            printf("(");
        } 
        for(int i=1;i<=p-1;i++){
            printf(")");
        }
        for(int i=1;i<=z;i++){
            printf("(");
        }
        printf(")");
    }
}