uva live 7637 Balanced String （贪心）

超、凢脫俗 2022-01-05 15:25 209阅读 0赞

题目链接：[https://icpcarchive.ecs.baylor.edu/index.php?option=com\_onlinejudge&Itemid=8&page=show\_problem&problem=5659][https_icpcarchive.ecs.baylor.edu_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_5659]

# 题意： #

你有一个只包含"(" 和 ")" 的串，每一个位置有个数值，这个数值是当前的左括号-右括号的值。

例：()() 数值就是1010。

给你一个打乱了的数值，要你构造出字典序最小的字符串。

# 题解： #

因为左括号比右括号小，所以我们要尽量的选择左括号，选择左括号会使得数值增大，如果这个数值不能继续增大了我们就只能选择右括号。

记得要初始化

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <string>
     5 #include <algorithm>
     6 #include <cmath>
     7 #include <vector>
     8 #include <queue>
     9 #include <map>
    10 #include <stack>
    11 #include <set>
    12 using namespace std;
    13 typedef long long LL;
    14 typedef unsigned long long uLL;
    15 #define ms(a, b) memset(a, b, sizeof(a))
    16 #define pb push_back
    17 #define mp make_pair
    18 #define eps 0.0000000001
    19 #define IOS ios::sync_with_stdio(0);cin.tie(0);
    20 const LL INF = 0x3f3f3f3f3f3f3f3f;
    21 const int inf = 0x3f3f3f3f;
    22 const int mod = 1e9+7;
    23 const int maxn = 100000+10;
    24 int a[maxn];
    25 int num[maxn];
    26 int last[maxn];
    27 int ans[maxn];
    28 void solve()
    29 {
    30     ms(num, 0);
    31     ms(last, 0);
    32     int n;scanf("%d", &n);
    33     for(int i = 0;i<n;i++)  scanf("%d", &a[i]);
    34     for(int i = 0;i<n;i++){
    35         if(a[i]<0){
    36             printf("invalid");return;
    37         }
    38     }
    39     for(int i = 0;i<n;i++){
    40         num[a[i]]++;
    41     }
    42     last[0]=0;
    43     for(int i=1;i<=n;i++){
    44         if(num[last[i-1]+1]){
    45             last[i] = last[i-1]+1;
    46             ans[i] = 1;
    47             num[last[i-1]+1]--;
    48         }
    49         else if(num[last[i-1]-1]){
    50             last[i] = last[i-1]-1;
    51             ans[i] = 0;
    52             num[last[i-1]-1]--;
    53         }
    54         else{
    55             printf("invalid");return;
    56         }
    57     }
    58     if(ans[n]==0){
    59         for(int i = 1;i<=n;i++)
    60             if(ans[i]==1)  printf("(");
    61             else    printf(")");
    62     }else{
    63         printf("invalid");return;
    64     }
    65 }
    66 int main() {
    67 #ifdef LOCAL
    68     freopen("input.txt", "r", stdin);
    69 //        freopen("output.txt", "w", stdout);
    70 #endif
    71 //    IOS
    72     int t;scanf("%d", &t);
    73     int cnt = 1;
    74     while(t--){
    75         printf("Case %d: ", cnt++);
    76         solve();
    77         printf("\n");
    78     }
    79     return 0;
    80 }

转载于:https://www.cnblogs.com/denghaiquan/p/7288100.html

[https_icpcarchive.ecs.baylor.edu_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_5659]: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5659
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/f7b6f72f2e1e4ee5bbc9ab12c87f5a95.png