Codeforces Round #600 (Div. 2) - B. Silly Mistake(模拟)

题意：有一个公司，每天有员工进出，$a[i]>0$时表示$a[i]$这个员工进入公司，$a[i]<0$时表示$-a[i]$这个员工出公司，公司对进出办公室有一些严格的规定

员工每天最多只能进入一次办公室
如果那天他没有进办公室的话，他显然不能离开
每天开始和结束时，办公室都是空的（员工不能呆在晚上），办公室也可能在一天中的任何时候都是空的

现在给你序列$a$（$a[i] \neq 0$），问你是否能够把数组$a$分为几个相邻的子数组，使得每一个子数组员工的进出情况符合要求并输出每一个子数组的长度，或者输出$-1$表示不可能

思路：用一个数组$mk$标记某个人状态，$mk[i]=0$表示$i$号员工在这一天内还没有操作，$mk[i]=1$表示$i$号员工在这一天内已经进入办公室，$mk[i]=-1$表示$i$号员工在这一天内已经进入办公室并且出去了，$num$记录此时办公室的人数，如果$num=0$时则可以进入新的一天，同时需要用一个数组$p$记录这一天已经出去的员工编号，在进入新的一天时，则需要将这些员工的$mk[i]$变为$0$，中间出现不合法的情况直接跳出循环，输出$-1$

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

const int N = ;

const int M = ;

int n, a[N], mk[M];

int num, cnt, p[N];

int res[N], pos;

int main()

{

    scanf("%d", &n);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]);

    int flag = ; res[++pos] = ;

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

        if (a[i] > ) {

            if ( == mk[a[i]]) {

                mk[a[i]] = , num++;

            }

            else {

                flag = ; break;

            }

        }

        else {

            if ( == mk[-a[i]]) {

                mk[-a[i]] = -, num--;

                p[++cnt] = -a[i];

                if ( == num) {

                    for (int j = ; j <= cnt; j++) mk[p[j]] = ;

                    cnt = , res[++pos] = i;

                }

            }

            else {

                flag = ; break;

            }

        }

    }

    if ( != num) flag = ;

    if (!flag) printf("-1\n");

    else {

        printf("%d\n", pos - );

        for (int i = ; i <= pos; i++) {

            printf("%d", res[i] - res[i - ]);

            printf(i == pos ? "\n" : " ");

        }

    }

    return ;

}

巴特西

Codeforces Round #600 (Div. 2) - B. Silly Mistake(模拟)

最新文章

热门文章