2018 Multi-University Training Contest 1 - B Balanced Sequence (贪心)

题意:对N个由(,)组成的字符串,求拼接后得到的最大的balance序列的长度。balance序列:空串/ A+B(A,B都是b序列)/ (+A+),A为b序列。此三种情况。

分析:在读入N每个字符串时,先将单独一个字符串中的b序列长度提取出来,记录其没有被使用的左弧L和右弧R的数目。因为要使其最后拼接后得到的子序列长度尽可能地大,那么按照贪心的思想,肯定希望左弧多的字符串在前,右弧多的字符串在后,所以要对其排序。但是排序时关键字的比较并不只是简单地比较二者的L与R,而且要先比较自身L与R的大小。

排完序后不断用之前已有的左弧去匹配当前字符串的右弧。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
const int maxn =1e5+;
struct Node{
int L,R;
bool f; //表示L>=R 和L<R的两种状态
bool operator < (const Node &rhs)const {
if(f){
if(!rhs.f) return true; //L>=R的状态要排在L<R之前
else return R<rhs.R; //状态相同则比较关键字R
}
else{
if(rhs.f) return false; //同理
else return L>rhs.L;
} }
}p[maxn]; //#define LOCAL
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T,N,M,u,v,tmp,K,cas=;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
int res=;
for(int i=;i<N;++i){
char op[maxn];
scanf("%s",op);
int L=,R=,len=strlen(op);
for(int j=;j<len;++j){
if(op[j]=='(') L++;
else{
if(L){L--;res+=;}
else R++;
}
}
p[i].L = L,p[i].R=R,p[i].f= (L>=R?true:false);
}
sort(p,p+N);
int preL=,tmp;
for(int i=;i<N;++i){
tmp = min(preL,p[i].R);
res+=*tmp;
preL-=tmp;
preL+=p[i].L;
}
printf("%d\n",res);
}
return ;
}
上一篇:Python输出和输入


下一篇:Springboot+shiro配置笔记+错误小结