CF-286C. Main Sequence（贪心，模拟）

洛谷传送门

CF传送门

---

解题思路

先考虑没有限制负数的情况，很显然就是用一个栈，每次与栈顶能配对就配对。

当有限制负数时，会出现错误，如 1 1 3 3 -1 -1，此时我们不能让前两个1相配对。

这是进行以下两个改动：

• 因为要求是正数在负数前面，所以我们进行倒序枚举。
• 若当前数要求为负数，则直接入栈。若为正数且与栈顶能配对，则直接配对，并把栈顶定为负数。

最后如果栈为空，则最终可以配对成功，否则不成功。

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
using namespace std;
const int maxn=1000005;
stack<int> s;
int n,m,a[maxn],vis[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    cin>>m;
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        vis[x]=1;
    }
    for(int i=n;i>=1;i--){
        if(s.empty()){
            s.push(i);
        }else{
            if(vis[i]) s.push(i);
            else if(a[i]==a[s.top()]){
                if(vis[i]==0){
                    vis[i]=1;
                    vis[s.top()]=-1;
                    s.pop();
                }else{
                    s.push(i);
                }
            }else{
                s.push(i);
            }
        }
    }
    if(!s.empty()){
        cout<<"NO"<<endl;
    }else{
        cout<<"YES"<<endl;
        for(int i=1;i<=n;i++) cout<<a[i]*vis[i]<<" ";
    }
    return 0;
}