【2022】贝壳找房秋招Java工程师笔试卷2

给定一个长度为 (一定是偶数) 的仅含有 "(" 和 ")" 的括号序列，其中，"(" 有 个，")" 也有 个。

牛牛可以进行若干次操作，每一次操作，选择一个下标 ，然后将该下标位置上的括号移动到整个序列的开头或者末尾。

那么，牛牛最少需要操作多少次，可以将该括号序列转化成一个常规括号序列？

"()" 是一个常规括号序列；
若 是一个常规括号序列，那么 "(" + + ")" 也是一个常规括号序列；
若 是一个常规括号序列， 也是一个常规括号序列，那么 也是一个常规括号序列。 输入描述： 本题为多组测试数据，第一行输入一个正整数 ，代表测试数据的组数。

对于每组测试数据，第一行输入一个正整数 ，代表括号序列的长度。
第二行输入一个长度为 的满足题意的括号序列。输入样例： 3 6 ()()() 6 )))((( 18 ))(((())()()()())( 输出描述： 对于每组测试数据，一行输出一个整数，代表需要的最小操作次数。输出样例 0 3 2

有一个 的矩形，矩形中的每个点初始值为 ，将每一行都分为若干块，每一块中，最多有一个点可以变化成 ，评判一个矩形质量的计算为：每一列中 的数量的平方和。

例如：一个 的矩形，第一行分成 三块，第二行分成 两块，第三行分成 两块。

那么，下述两种挑点转化成 的方案都是合法的：





而下述方案是不合法的



由于 这个点和 这个点属于同一块，而一块中最多只能出现一个 ，所以不合法。

对于上述两种合法方案而言，第一种方案的矩形质量为：
第二种方案的矩形质量为：

其中，第二种方案的矩形质量是当前分块状态下的最大值，该变化方案称之为最佳配置，显然，最佳配置的方案可能不唯一，但是，同为最佳配置的矩形质量一定是相同且最大的。

那么，对于一种矩形分块的情况，它最佳配置下的矩形质量可以达到多少？ 输入描述： 对于每组测试数据，第一行输入两个正整数 ，代表矩形的行、列长度。

接下去输入 行的分块信息，对于矩形的第 行而言，第一行输入一个正整数 ，代表第 行分成了 块。
接下去 行，每行两个正整数 ，代表第 行的某一分块的起点和终点(闭区间)。

数据保证，每一行的分块区间一定不重叠，且覆盖了 列。输入样例： 3 5 3 1 2 3 4 5 5 2 1 2 3 5 2 1 3 4 5 输出描述： 一行输出一个整数代表某一种最佳配置下的矩形质量。输出样例 19

牛牛拥有 根木棒，长度分别为

现在，牛牛可以做若干次操作，每一次操作，可以选择任意两根木棒，将它们拼接在一起，假设选择的两根木棒的长度分别为 ，那么拼接后的木棒长度为

那么，在停止操作之后，牛牛最多可以得到几根长度相同的木棒？ 输入描述： 本题为多组测试数据，第一行输入一个正整数 ，代表测试数据的组数。

接下去 行，每行一个正整数 ，代表木棒的数量，同时表明，木棒的长度分别为 输入样例： 2 1 3 输出描述： 对于每组测试数据，一行输出一个整数代表答案。输出样例 1 2

共有件物品，每件物品价值为。你共有次机会，每次可以拿一件物品，但如果你第次拿的物品价值超过（严格大于），则后续的第次机会将作废，从第次开始才可以继续拿物品。你每次可以拿任意一件物品，现在想知道在此规则下，你能拿到的物品总价值最大是多少？ 输入描述： 第一行三个正整数，物品数和机会数，后续作废次，价值阈值；
第二行个正整数，每件物品的价值。
输入样例： 5 2 10 5 8 10 15 33 输出描述： 一个正整数，表示拿到的物品最大总价值。输出样例 58