526互联

Educational Codeforces Round 152 (Div. 2) D. Array Painting（双指针）

发布时间 2023-10-10 10:41:54作者: ikunhuaji

Educational Codeforces Round 152 (Div. 2) D. Array Painting

//思路：双指针找连续正数段
//若段中出现2，则更新两头的0的情况，若为涂色则改为true
//若无2，则优先更新左侧0，若左0已经为true，则更新右侧0
//数组开头结尾特判
#define int long long
#define ld long double

using namespace std;

bool st[200010];
int a[200010];

void op()
{
	int n;
	cin >> n;

	int cnt = n;
	for (int i = 1; i <= n; i++)cin >> a[i];

	int k = 0;

	for (int i = 1; i <= n; i++)
	{
		if (a[i] > 0)
		{
			k++;
			if (a[i] == 2)
			{
				if (i - 1 != 0 && !st[i - 1])
				{
					cnt--;
				}
				int fg = 0;
				for (int j = i + 1; j <= n; j++)
				{
					if (a[j] == 0)
					{
						
						st[j] = true;
						cnt -= (j - i + 1);
						
						fg = j;
						break;
					}
				}
				if (fg)i = fg;
				else
				{
					cnt -= (n - i + 1);
					i = n;
				}
			}
			else if (a[i] == 1)
			{
				if (i-1!=0&&!st[i - 1])cnt--;
				int fg = 0;
				bool fg2 = false;
				for (int j = i + 1; j <= n; j++)
				{
					if (!fg2 && a[j] == 2)fg2 = true;
					if (a[j] == 0)
					{
						cnt -= (j - i);
						if (a[j - 1] == 2 || (i - 1 != 0 && st[i - 1]) || i - 1 == 0 || fg2)
						{
							cnt--;
							st[j] = true;
						}
						fg = j;
						break;
					}
				}

				if (fg)i = fg;
				else
				{
					cnt -= (n - i + 1);
					i = n;
				}
			}
		}
	}

	cout << k + cnt << endl;
}

signed main()
{
	op();
	return 0;
}