admin 管理员组文章数量: 887021
括号
括号
from：
时间限制：c/c++ 1s，其他 2s
空间限制：c/c++ 256M，其他512M
题目描述：
请你构造一个非空的括号字符串，包含正好 k 个不同合法括号对。
所谓括号字符串，是指由’(‘和’)'这两种字符构成的字符串。
要求构造的字符串长度不超过100000。
输入描述：
一个整数 k。
0 <= k <= 10^9
输出描述：
一个仅包括左右括号字符串，其中有k个合法的括号对。如果有多种构造方法，输出任意一种合法方案即可。
样例1
//输入：
3
//输出：
()()
//说明：
/*
假设字符串下标从1开始，则（1，2），（1，4），（3，4）共计三个合法括号对。
当然 ()))也是一种合法的构造。
*/
样例2
//输入：
4
//输出
(())
样例3
//输入
9
//输出
()))))))))
思路：
这个题目是典型的考思路，构造一个字符串。
我们应该如果来构造呢？
可以想到的是:
() 有1 * 1 个括号
(()) 有2 * 2 个括号
((())) 有3 * 3 个括号
以此类推......
题目所说的k <= 10 ^ 9，开方是小于10 ^ 5 的
但是输入的数据不全是平方数啊，那这个时候应该如何处理呢？
那我们每次都在一个平方数的基础上再加上若干个括号，那么我们首先要找到平方不大于k的那个数。
比如：
//样例1
k = 3
那么我们用1 * 1
() 在此基础上我们还差两个括号，就在左括号的右边插入右括号
插入第一个：())
插入第二个：()))
这样就得到答案了
//样例2
k = 4
我们用到2 * 2
(()) 这个时候已经刚好等于4了，所以不需要再继续补了
//自己举的例子
k = 5
我们用到2 * 2
(()) 这个时候是还差一个括号的
那么我们就在第一个左括号的后面插入一个右括号，让这个插入的右括号和它前面的左括号组成一个完整括号
()())
也就是先找到一个 x * x，然后差几个再去补，插入进去就可以了
**注意：**这里可能会补很多次，比如k等于63的时候，我们选择7 * 7，还差63 - 49 = 14，而一共只有7个左括号，所以每次最多只能补上7个括号，这样子一次是补不完的，要分多次补，但是很简单，一个while就完事儿了。
话不多说，上代码！
AC代码：
#include<iostream>
#include<string>
using namespace std;
int main() {long long n, m = 1, p;cin >> n;if (n == 0){cout << "(";return 0; //如题中所述，输出字符串为非空}while (m * m <= n) ++m;--m; //找到平方不大于n的最大mstring s;for (int i = 1; i <= m; ++i)s += '(';for (int i = 1; i <= m; ++i)s += ')'; //两个循环构建了m ^ 2 个个括号p = n - m * m; //p表示还需要多少对括号while (p) { //如果m ^ 2 个括号还不够，就继续补充if (p >= m)s.insert(m, ")"), p -= m;elses.insert(p, ")"), p = 0;}cout << s;return 0;
}
应该还会有很多其他方法，欢迎指教！
本文标签： 括号
版权声明：本文标题：括号 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687636736h123481.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论