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

B. Silly Mistake

题目大意:

首先定义有效的一天:

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

每一个人不能过夜

 

不合理:

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

 

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

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

 

题目思路:

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

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

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

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

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

B. Silly Mistake  Codeforces Round #600 (Div. 2)
#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

 

上一篇:Codeforces Round #600 (Div. 2)


下一篇:Codeforces Round #600 (Div. 2)