牛客小白月赛4 I 合唱队形思维字符串-白红宇

牛客小白月赛4 I 合唱队形思维字符串

阅读量：5931 次

发布时间：2019-06-19

本文共 2059 字，大约阅读时间需要 6 分钟。

链接：

来源：牛客网

题目描述

铁子的班级在毕业晚会有一个合唱节目，到了毕业晚会的时候，他们必须排成一排一起合唱"认错"，"当然是选择原谅他"等一系列原谅歌曲，但是当队形布置好的时候，领导们觉得队形里最长的连续的女生的长度太小了，但是由于马上要开始演唱，所以最多只能两个人交换位置，问新队形中最长的连续的女生的长度是多少？

输入描述:

第一行一个数字n表示铁子班级的总人数。1≤n≤10

⁵

第二行一个字符串s表示最初的队形布置，si=0表示第i个人是女生，si=1表示第i个人是男生。

输出描述:

输出一行表示答案

示例1

输入

输出

说明

将第6个女生和第3个男生交换位置可以满足要求 分析：考虑分离字符串，将一串只含0，1的字符串中每段连续的1和连续的0的字符串分离出来，即保存下每一段连续的长度 　　此时：如果分离出的0连续的字符串数是0，答案就是0 　　　　如果分离出0连续的字符串数是1，答案就是e[0]，代表那一段连续的0的个数 　　　　如果分离出0连续的字符串数是2，答案就是max(e[0],e[1])+1，边上的一个字符可以被替换成0 　　　　如果大于2，因为只能交换两个字符，所以考虑取单独的+1和两个中间只隔1个不同的相加再加一（此时交换一个字符后两个连续字符串可以合并起来）的最大值 AC代码：

#include #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 1e5+10;const ll mod = 998244353;const double pi = acos(-1.0);const double eps = 1e-8;vector
                       
                         e, d; //e保存每段连续0的个数，d保存每段连续1的个数string s;int main() { ios::sync_with_stdio(0); ll n; while( cin >> n ) { e.clear(); d.clear(); cin >> s; ll cnt = 0, num = 0, flag = false; for( ll i = 0; i < n; i ++ ) { if(!flag) { if( s[i] == '0' ) { if(num) { d.push_back(num); } num = 0, cnt ++, flag = true; if( i == n-1 ) { e.push_back(cnt); } } else { num ++; } } else { if( s[i] == '0' ) { cnt ++; if( i == n-1 ) { e.push_back(cnt); } } else { e.push_back(cnt); num ++, cnt = 0, flag = false; } } } if( e.size() == 0 ) { cout << 0 << endl; } else if( e.size() == 1 ) { cout << e[0] << endl; } else if( e.size() == 2 ) { cout << max(e[0],e[1])+1 << endl; } else { ll maxnum = e[0]; ll j; if( s[0] == '1' ) { j = 1; } else { j = 0; } for( ll i = 1; i < e.size(); i ++, j ++ ) { if( d[j] == 1 ) { maxnum = max(maxnum,e[i]+e[i-1]); } else { maxnum = max(maxnum,e[i]); } } cout << maxnum+1 << endl; } } return 0;}/*100010111000*/

转载于:https://www.cnblogs.com/l609929321/p/9531902.html

你可能感兴趣的文章