怎么给网站做 360快照,asp.net做的网站文字控件随窗口大小不变化,成都装饰网站建设,桂林两江四湖景区题意#xff1a; t组测试数据#xff0c;每组数据有 n 个只由 ( 和 ) 构成的括号串。 要求把这 n 个串排序然后组成一个大的括号串#xff0c;使得能够匹配的括号数最多。 如()()答案能够匹配的括号数是 4#xff0c;(()) 也是 4。 例如#xff1a; n 2 ) )(( 你可以将其…题意 t组测试数据每组数据有 n 个只由 ( 和 ) 构成的括号串。 要求把这 n 个串排序然后组成一个大的括号串使得能够匹配的括号数最多。 如()()答案能够匹配的括号数是 4(()) 也是 4。 例如 n 2 ) )(( 你可以将其排序为))((数目为0也可以将其排序为)(()数目为1。 解法 贪心。 把所有字符串中本身能够匹配的括号全部去掉然后剩下的字符串只有三种 1、全是 ( 2、全是 ) 3、一串 ) 加一串 ( 对于每一种字符串如果 ( 的数目多于 ‘)’就把它放在前面按照字符串中的 ‘)’ 从小到大排序。 如果 ) 的数目多于 ‘(’就把它放在后面按照字符串中的 ‘(’ 从大到小排序。 然后统计新串合法的括号数即可。 #include iostream
#include cstdlib
#include cstdio
#include cmath
#include algorithm
using namespace std;#define maxn 100000 1000struct Node
{int x, y;
}a[maxn];bool cmp(Node a, Node b)
{if (a.x-a.y 0 b.x-b.y 0) return true; if (a.x-a.y 0 b.x-b.y 0) return false; // 左括号数目右括号数目的一定在右括号左括号的前面 if (a.x-a.y 0 b.x-b.y 0) return a.y b.y; //都是左括号比有括号多按照右括号的数量从小到大排序if (a.x-a.y 0 b.x-b.y 0) return a.x b.x; //都是左括号比右括号少按照左括号的数量从大到小排序
}int main()
{int t;scanf(%d, t);for (int ca 1; ca t; ca){int n, ans 0;scanf(%d, n);for (int i 1; i n; i){char s[maxn];scanf(%s, s);a[i].x a[i].y 0; //a[i].x 记录左括号的数量 a[i].y 记录右括号的数量。for (int j 0; s[j] ! \0; j)if (s[j] )){if (a[i].x) {a[i].x--; ans;}else a[i].y;}else a[i].x; //括号匹配}sort(a1, a1n, cmp);int instack 0;for (int i 1; i n; i){if (a[i].y instack){ans min(a[i].y, instack);instack max(0, instack-a[i].y);}instack a[i].x;} //最后进行一次括号匹配继续统计答案。printf(%d\n, ans * 2);}} 转载于:https://www.cnblogs.com/ruthank/p/9371156.html
