1399D - Binary String To Subsequences(队列)

题目

思路:看数据大小1e5可以知道我们需用O(n)或O(nlogn)的算法。故开两个队列,q0,q1,一个表示存储以0结尾一个存储以1结尾,当队列空时另增加一个新的子序列,不为空时将转变一个序列从q0->q1(当遇到1且q0中还剩下xxxx0的字序列时,不剩则再增加一个子序列),细节见代码。

Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<vector>
#include<queue>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;
int lst[Max], ls[Max];
int b[Max];

int main()
{
   
	FAST;
	int t;cin >> t;
	while (t--)
	{
   
		int n;cin >> n;
		for (int i = 1;i <= n;i++)
		{
   
			char a;cin >> a;lst[i] = a - '0';
		}
		queue<int> q0, q1;int x = 0;
		for (int i = 1;i <= n;i++)
		{
   
			if (lst[i] == 0)
			{
   
				if (q1.size() == 0)
				{
   
					q0.push(++x);
					b[i] = x;
				}
				else
				{
   
					q0.push(q1.front());
					b[i] = q1.front();
					q1.pop();
				}
			}
			else
			{
   
				if (q0.size() == 0)
				{
   
					q1.push(++x);
					b[i] = x;
				}
				else
				{
   
					q1.push(q0.front());
					b[i] = q0.front();
					q0.pop();
				}
			}
		}
		cout << x << endl;
		for (int i = 1;i <= n;i++)cout << b[i] << " ";
		cout << endl;
	}

		
}

全部评论

相关推荐

点赞 评论 收藏
分享
北漂的牛马人:211佬,包进的,可能是系统问题
点赞 评论 收藏
分享
见见123:简历没有啥问题,是这个社会有问题。因为你刚毕业,没有工作经历,现在企业都不要没有工作经历的。社会病了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务