P6956 题解

· · 题解

题目分析

输入 n 个数字 a_1,a_2,a_3...a_n，如果如果 a_i 为正，相当于往仓库在放入一个数字 a_i ,如果 a_i 为负，相当于从仓库中取出一个数字 -a_i ,如果 a_i 为 0，那么相当于往仓库中放入一个万能的数字，如果要取出一个仓库中没有的数，可以用 0 代替。

显然，可以用一个 visit 数组表示仓库中 visit_i 这个数的个数，out 数组表示 0 代替的数，遇到负数 i 时先看 visit_{-i} 是否大于 0。如果大于 0 就优先消耗仓库中 -i 的个数，即 visit[i]--，实在 -i 没有了，再看有没有代替的 0。如果连 0 都没有了，那一定无法完成，输出 No，否则 0 的个数减一，将这个 0 代替的数（也就是 -i 加入 out 数组中）。

代码

#include<bits/stdc++.h>
using namespace std;
int n,visit[100001]={0},a[100010],timesOf0=0,h=0,outOf0[100001]={0},no=0,yes=1;
int main(){
    cin>>n;
    while(n--){
        int temp;
        cin>>temp;
        if(no==1){
            continue;
        }
        if(temp<0){
            if(visit[-temp]>=1){
                visit[-temp]--;
                continue;
            }
            if(timesOf0>0){
                timesOf0--;
                outOf0[h++]=-temp;
                continue;
            }
            cout<<"No";
            no=1;
            yes=0;
        }
        if(temp==0){
            timesOf0++;
        }
        if(temp>0){
            visit[temp]++;
        }
    }
    if(yes==0){
        return 0;
    }
    cout<<"Yes"<<endl;
    for(int i=0;i<h;i++){
        cout<<outOf0[i]<<" ";
    } 
    return 0;
}

这样就能 AC 吗？不行。这样会出现wrong output format Unexpected end of file - int32 expected的错误。因为题目其实要求是：输出用过的 0 所代替的数字后，还要把没用过的 0 表示的数也输出。显然输出任何数都可以。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,visit[100001]={0},a[100010],timesOf0=0,h=0,outOf0[100001]={0},no=0,yes=1;
int main(){
    cin>>n;
    while(n--){
        int temp;
        cin>>temp;
        if(no==1){
            continue;
        }
        if(temp<0){
            if(visit[-temp]>=1){
                visit[-temp]--;
                continue;
            }
            if(timesOf0>0){
                timesOf0--;
                outOf0[h++]=-temp;
                continue;
            }
            cout<<"No";
            no=1;
            yes=0;
        }
        if(temp==0){
            timesOf0++;
        }
        if(temp>0){
            visit[temp]++;
        }
    }
    if(yes==0){
        return 0;
    }
    cout<<"Yes"<<endl;
    for(int i=0;i<h;i++){
        cout<<outOf0[i]<<" ";
    }
    for(int i=0;i<timesOf0;i++){
        cout<<1<<' ';
    }
    return 0;
}