HDU-6299 Balanced Sequence(贪心)Balanced Sequence

71 阅读 0 评论 47 点赞

我是靠谱客的博主要减肥老师，最近开发中收集的这篇文章主要介绍HDU-6299 Balanced Sequence(贪心)Balanced Sequence，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Balanced Sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5357 Accepted Submission(s): 1381

Problem Description

Chiaki has n strings s1,s2,…,sn consisting of '(' and ')'. A string of this type is said to be balanced:

+ if it is the empty string
+ if A and B are balanced, AB is balanced,
+ if A is balanced, (A) is balanced.

Chiaki can reorder the strings and then concatenate them get a new string t. Let f(t) be the length of the longest balanced subsequence (not necessary continuous) of t. Chiaki would like to know the maximum value of f(t) for all possible t.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤105) -- the number of strings.
Each of the next n lines contains a string si (1≤|si|≤105) consisting of `(' and `)'.
It is guaranteed that the sum of all |si| does not exceeds 5×106.

Output

For each test case, output an integer denoting the answer.

Sample Input

)()(()(

)

)(

Sample Output

Source

2018 Multi-University Training Contest 1

思路：我们再输入的时候直接累加每个字符串的价值（字符串内已经匹配成功），剩余的字符串必定是（“))))(((((”）的形式，我们用结构体记录仪下每个字符串左括号与右括号的个数，排序后，在用贪心的思想计算价值总和。

1.左括号少于右括号时，尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。

2.左括号多于右括号时，也尽可能让右括号多的排在前面，同时如果此时右括号相同，再优先将左括号少的排在前面。

3.左右括号数相同等时，将数量多的排在前面。

4.如果遇到以上三种混合的情况，按照1->2->3的优先级进行排序。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define clr(a) memset(a,0,sizeof(a))
const int maxn = 1e6+10;
 
int t,n;
struct node{
    int l,r;
}p[maxn];
 
int ans ;
bool cmp (node a,node b){
    if(a.l >= a.r && b.l < b.r)    return false;//左括号多于右括号，交换
    if(a.l < a.r && b.l >= b.r)    return true;//右括号多于左括号，不交换
    if(a.l >= a.r && b.l >= b.r) return a.r > b.r;//按照右括号从多到少排列
    return a.l < b.l;//否则及按照左括号由少到多排列
}
int main(){
    scanf("%d",&t);
    while(t--){
        ans = 0;
        clr(p);
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            char s[maxn];
            scanf("%s",s);
            int len = strlen(s);
            for(int j=0;j<len;j++){
                if(s[j]=='('){
                    p[i].l ++;
                }
                else{
                    if(p[i].l > 0){
                        ans += 2;
                        p[i].l --;
                    }
                    else{
                        p[i].r ++;
                    }
                }
            }
        }
        sort(p,p+n,cmp);
        int temp = p[0].r;
        for(int i = 1 ; i < n ; i ++){
            if(p[i].l > temp){
                ans += 2*(temp);
                temp = p[i].r;
            }
            else{
                ans += 2*(p[i].l);
                temp = temp - p[i].l + p[i].r;
            }
        }
        cout<<ans<<endl;
    }
 
    return 0;
}