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;
}
- 指针 Educational Codeforces Painting Arrayeducational codeforces painting array 指针educational codeforces painting educational codeforces painting round educational codeforces reodering array painting 1479b array the educational codeforces round rated educational codeforces round 151 construction educational codeforces round educational codeforces round 147 cf-educational educational codeforces round