题目大意:
首先定义有效的一天:
每一个不同的数字只能进去一次,出来一次,正数代表进去,负数代表出来
每一个人不能过夜
不合理:
一个数字只有进去,或者只有出来则是无效的
给你一个数组,让你把数字分成若干个有效天,不要求最大化这个天数,也不要求最小化这个天数,
问怎么划分,如果无法划分则输出-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 + ; bool in[maxn];
int last[maxn]; vector<int>ans; void fail(){
printf("-1\n");
exit();
}
//正负一对,以负的结尾
int main(){
int n,ptr=,tot=;//ptr记录上一次截断的位置,tot记录这个时候是否成对的出现
scanf("%d",&n);
for(int i=;i<=n;i++){
int x;
scanf("%d",&x);
if(x>){
if(in[x]) fail();//如果之前进入了,现在继续进入是不对的
if(last[x]>ptr) fail();//这个是判断上一对是否和这一对会在一天,如果ptr<last[x],则说明在同一天
in[x]=;//表示这个进入
tot++;//表示对数+1
}
else {
x=abs(x);
if(!in[x]) fail();//如果从未进入过,则不能出去
tot--;//合并
in[x]=;//表示已经出去
last[x]=i;//表示这一对的结束位置,便于后面ptr的判断
}
if(tot==){
ans.push_back(i-ptr);//这个题目不要求最少的天数,所以直接加上去就可以了
ptr=i;//ptr更新
}
}
if(tot>) fail();
printf("%d\n",ans.size()*);
for(int i=;i<ans.size();i++) printf("%d ",ans[i]);
printf("\n");
return ;
}