B.Silly Mistake

题目：愚蠢的错误##

题意：中心公司有一个办公室有一个成熟的安全系统，这里面有10^{6个雇员，编号从1到10}6

安全系统有入口和出口，数字i表示第i个雇员进入，-i表示第i个雇员出去

公司有一些严格的规矩：

1.雇员一天可以进入办公司最多一次

2.如果今天雇员没进雇员，他是无法出去的

3.办公室空的，代表里面的人都出去了

[1, 7, -7, 3, -1, -3]表示一个有效的一天，1进入，7进入，7出去，3进入，1出去，3出去

这里有a1，a2，...，an表示它们进出的序列，这个序列表示一天或者多天

你必须把这个序列划分成多天

例如：a = [1, -1, 1, 2, -1, 2, 3, -3]可以被划分成[1, -1| 1, 2, -1, -2, 3, -3]，

即两天

如果没有有效的划分，输出-1

如果有有效的划分，输出划分的天数和每段的元素个数，如果有多个答案，输出一种就行(暗示贪心)

分析：解决这个问题有一种直观的贪心做法，模拟序列的进出，只要办公室出现一次空的，就记录划分的段数，

新开一天

为了有效地模拟这个问题，我们可以给予数组中每个雇员三种状态：进入办公室/在办公室里/离开办公室

每当我们结束一天，只需要重置参与的员工的状态

时间复杂度:O(n + e)

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

const int N = 1000005;

int n;

vector<int> off;//办公室

vector<int> sec;//段

int state[N];//每个雇员的状态

const int WAIT = 0, ENTERED = 1, LEFT = 2;

int solve()

{

	scanf("%d", &n);

	int len = 0;

	int em;//雇员

	for (int i = 1; i <= n; ++i)

	{

		cin >> em;

		int guy = abs(em);

		off.push_back(guy);

		if (em > 0)//进入

		{

			if (state[guy] != WAIT)return false;

			state[guy] = ENTERED;

			++len;

		}

		else {//出去

			if (state[guy] != ENTERED)return false;

			state[guy] = LEFT;

			--len;

		}

		if (len == 0)

		{

			sec.push_back(off.size());

			for (int x : off)state[x] = WAIT;

			off.clear();

		}

	}

	if (!off.empty())return false;

	int nDays = sec.size();

	cout << nDays << endl;

	for (auto t : sec)

	{

		cout << t << " ";

	}

	return true;

}

int main()

{

	if (!solve())

		cout << "-1\n";

	return 0;

}

巴特西

B.Silly Mistake

题目：愚蠢的错误##

最新文章

热门文章