CF 286C(Main Sequence-贪心括号匹配)
贪心,从后向前做,尽可能取左括号。
#include<cstdio>include<cstring>
include<cstdlib>
include<iostream>
include<functional>
include<algorithm>
include<stack>
using namespace std;
define MAXN (1000000+10)
define MAXP (1000000000+10)
int n,m,a[MAXN],ans[MAXN],tot; bool b[MAXN]; int s[MAXN],size=0; int main() { memset(b,0,sizeof(b)); scanf("%d",&n);tot=n+1; if (n%2) {printf("NO\n");return 0;} for (int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for (int i=1;i<=m;i++) { int p; scanf("%d",&p); b[p]=1; } for (int i=n;i;i--) { if (size==0||s[size]!=a[i]||b[i]) { s[++size]=a[i];ans[--tot]=-a[i]; } else ans[--tot]=s[size--]; } if (size) printf("NO\n"); else { printf("YES\n"); for (int i=1;i<n;i++) printf("%d ",ans[i]);printf("%d\n",ans[n]); }
return 0;
}
发表评论