P6956 题解

· · 题解

题意

若 a_i 为正数，提供一个价值为 a_i 的物品。

若 a_i 为负数，消耗一个价值为 a_i 的物品。

若 a_i 为 0，选择一个价值随意的物品。

要求判断所有 a_i 为负数时的操作能否完成。

思路

很简单，开桶来记录每次的提供与消耗。但是，a_i 为 0 时选择的物品会影响到后面 a_i 为负数的情况。那么我们就可以换种思路：在 a_i 为 0 时先不取物品，到后面 a_i 为负数时，价值为 a_i 的物品不够了，我们再拿前面 a_i 为 0 时的操作来补救。本题就轻松解决了。

陷阱

有可能出现价值随意的物品多余的情况，随意输出即可，本蒟蒻输出的是 1000。

代码

#include<bits/stdc++.h>
using namespace std;
int n,t,i,x,sum,f[1010],a[1010];
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>x;
        if(x>0)f[x]++;//为正数时价值为x的物品数量加一 
        else if(x<0){
            if(f[-x]>0)f[-x]--;//数量足够，就消耗掉一个 
            else{
                if(sum>0)a[++t]=-x,sum--;//拿前面价值随意的物品来补救 
                else{cout<<"No";return 0;}//救不了输出No 
            }
        }
        else sum++;//价值随意的物品个数加一 
    }
    cout<<"Yes\n";
    for(i=1;i<=t;i++)
        cout<<a[i]<<" "; 
    while(sum>0)cout<<"1000 ",sum--;
}