B. Silly Mistake

题目大意：

首先定义有效的一天：

每一个不同的数字只能进去一次，出来一次，正数代表进去，负数代表出来

每一个人不能过夜

 

不合理：

一个数字只有进去，或者只有出来则是无效的

 

给你一个数组，让你把数字分成若干个有效天，不要求最大化这个天数，也不要求最小化这个天数，

问怎么划分，如果无法划分则输出-1

 

题目思路：

这个题目我觉得不是很简单，反正我写的比较吃力

首先我们要模拟这个进入和出去，则可以用一个bool数组，为真则是进去，为假则是出去。

其次我们要判断是不是同一天，用一个ptr来表示上一天的最后一天，一个last数组来表示上一对数的最后一天的位置，如果有两个数放在了同一天，则判断无法划分

再而我们要判断这一段划分出来的数组是不是一一对应，这个则有tot，tot+表示进去，tot-表示出去，如果tot==0 则表示划分出去的一段是一一对应的。

因为不要求划分天数尽量小，所以可以tot==0则划分一次，ptr相应进行改变。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <cmath>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int M=1e6;
const int maxn = 1e6 + 10;

bool in[maxn];
int last[maxn];

vector<int>ans;

void fail(){
    printf("-1\n");
    exit(0);
}
//正负一对，以负的结尾
int main(){
    int n,ptr=0,tot=0;//ptr记录上一次截断的位置，tot记录这个时候是否成对的出现
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        if(x>0){
            if(in[x]) fail();//如果之前进入了，现在继续进入是不对的
            if(last[x]>ptr) fail();//这个是判断上一对是否和这一对会在一天，如果ptr<last[x]，则说明在同一天
            in[x]=1;//表示这个进入
            tot++;//表示对数+1
        }
        else {
            x=abs(x);
            if(!in[x]) fail();//如果从未进入过，则不能出去
            tot--;//合并
            in[x]=0;//表示已经出去
            last[x]=i;//表示这一对的结束位置，便于后面ptr的判断
        }
        if(tot==0){
            ans.push_back(i-ptr);//这个题目不要求最少的天数，所以直接加上去就可以了
            ptr=i;//ptr更新
        }
    }
    if(tot>0) fail();
    printf("%d\n",ans.size()*1);
    for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}

View Code