Problem 1

题目描述：西电近期举办了一次编程比赛，参加比赛的选手有3*n个选手，每个选手都有一个水平值a_i。现在要将这些选手进行组队，一共组成n个队伍，即每个队伍3人。老师发现队伍的水平值等于该队伍队员的第二高水平值。

一个队伍三个队员的水平值分别是3,3,3，那么队伍的水平值是3；

一个队伍三个队员的水平值分别是3,2,3，那么队伍的水平值是3；

一个队伍三个队员的水平值分别是1,5,2，那么队伍的水平值是2。

为了让比赛更有看点，老师就想安排队伍使所有队伍的水平值总和最大。

输入描述：输入的第一行为一个正整数n（1<=n<=10^5^），输入的第二行包括3*n个整数a_i（1<=a_i<=10^9^），表示每个参赛选手的水平值。

输出描述：输出一个整数表示所有队伍的水平值总和最大值。

样例输入：

5 2 8 5 1 5

样例输出：

思路：就是取n个第二大的数，leetcode有一道十分相似的题目。【排序后，取隔三个取第二大即可】

代码：

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;
int main(){
	int n,num;
	scanf("%d",&n);
	n*=3;
	vector<int> nums;
	while(n--){
		scanf("%d",&num);
		nums.push_back(num);
	}
	sort(nums.begin(),nums.end());
	// 取第n-2 n-5 ……1号元素
	int sum=0;
	for(int i=nums.size()/3;i<nums.size()/3*2;++i){
		sum+=nums[i];
	}
	printf("%d\n",sum);
	return 0;
}

Problem 2

题目表述：一个数组有N个元素，求连续子数组的最大和。例如：【-1,2,1】，和最大的连续子数组为【2,1】，其和为3.

输入描述：输入为两行。第一行为一个整数n（1<=n<=100000），表示一共有n个元素，第二行为n个数，即每个元素，每个整数都在32位int范围内，以空格分隔。

输出描述：所有连续子数组中和最大的值。

样例输入：

-1 2 1

样例输出：

算法思路：

不能用滑动窗口，必须用动态规划实现O（n）。

状态定义：dp[i]表示以下标i结尾的所有子数组的最大和

状态转移方程：dp[i]=max(dp[i-1]+nums[i],nums[i])

代码：

#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;
int main(){
	int n,num;
	scanf("%d",&n);
	vector<long long> nums;
	while(n--){
		scanf("%d",&num);
		nums.push_back(num);
	}
	vector<long long> dp(nums.size(),0);
	dp[0]=nums[0];
	long long re=dp[0];
	for(int i=1;i<nums.size();++i){
		dp[i]=max(dp[i-1]+nums[i],nums[i]);
		re=max(dp[i],re);
	}
	printf("%d",re);
	return 0;
}

Problem 3

题目描述：输入一个长度为n的字符串（0<=n<=20）只包含’(‘和’)’。对于这个字符串如”(())”，“()()”是匹配的，”)(“，“())(”都不是括号匹配的。

删除最左边的’(‘，从剩下的字符串中删除任意的’)’，使得删除后的字符串仍然是括号匹配的。

对整个字符串重复该删除操作，知道删除了整个字符串。问这样的括号匹配方案有多少个？（只要有一次删除的有括号’)’不同则认为是一个不同的方案）。

输入描述：

输出描述：

样例输入：

1.(((())))

2.()()()

样例输出：

1.24

2.1

算法思路

代码