【Codeforces Round #469 (Div. 2)】C. Zebras（贪心，思维）

【Codeforces Round #469 (Div. 2)】C. Zebras（贪心，思维）

题意： 给长为n（<=2e5）由0，1组成的字符串，求分割成以0开头和结尾并且0，1交替出现的若干个字符串，要求它们的位置是递增的。 分析： 贪心， 赛时各种特判，因为写的代码 太烂，然后就卡在第八组数据。 改不动了，改完后最坏情况下复杂度成了O(n^2) 而大多数大佬 代码比较优美 使用vector记录下标，不能用普通数组， 爆内存 贪心思路：RT，以0开头，若有多个0连续，则分割数+1；若出现1，RT，放在0后面，此时检查是否还有以0结尾的字符串，若没有，输出-1，结束。 若有，加到0后面，分割数-1 见代码： #include using namespace std; #define mem(a,n) memset(a,n,sizeof(a)) #define memc(a,b) memcpy(a,b,sizeof(b)) #define rep(i,a,n) for(int i=a;ivec[N]; char s[N]; int main() { while(~scanf("%s",s)) { rep(i,0,N) vec[i].clear(); int cnt=0,ans=0; for(int i=0; s[i]; i++) { if(s[i]=='0') vec[++cnt].pb(i+1); else { if(cnt==0) return 0*puts("-1");///cnt代表以0结尾的字符串的个数 vec[cnt--].pb(i+1); } ans=max(ans,cnt); } if(ans!=cnt)///满足此条件 说明有以'1'结尾的字符串 return 0*puts("-1"); printf("%d\n",ans); for(int i=1; i<=ans; i++) { printf("%d",vec[i].size()); for(auto x:vec[i]) printf(" %d",x); puts(""); } } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。