Codeforces 1167D - Bicolored RBS

题目链接：http://codeforces.com/problemset/problem/1167/D

题意：题目定义RBS，给你一个字符串，你要对其所有字符染色，使之分解为俩个RBS，使俩个RBS深度最大值（内括号）最小化，用0和1输出染色方案。

思路：贪心，从左往右遍历，一边分一个，用 m 统计 ‘（ ’ 的数量，m为奇数分给左边，偶数分给右边，为了满足俩边左右括号数目能一致，当遇到 ‘ ）’的时候应该先和最近的 ‘（ ’配对，再调整 m。

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int main()

 {

     string a;

     int n;

     cin >> n >> a;

     int m = ;

     for(int i = ;i < a.size();i++)

     {

         if(a[i] == '(')

         {

             m++;

             cout << m % ;

         }

         else

         {

             cout << m %  ;

             m--;

         }

     }

     return  ;

 }

巴特西

Codeforces 1167D - Bicolored RBS

最新文章

热门文章