链接：https://ac.nowcoder.com/acm/contest/11253/K
来源：牛客网
题目描述
ZYT had a magic permutation a1,a2,⋯ ,ana1,a2,⋯,an, and he constructed a sequence b1,b2,⋯bnb1,b2,⋯bn by the following pseudo code:
Stk is an empty stack for i = 1 to n : while ( Stk is not empty ) and ( Stk's top > a[i] ) : pop Stk push a[i] b[i]=Stk's sizeBut he somehow forgot the permutation aa, and only got some kk elements of bibi.
Construct a permutation aa satisfying these bibi , or determine no such permutation exists.
Here a permutation refers to a sequence that contains all integers from 11 to nn exactly once.
输入描述:
The first line contains two integers nn,k(1≤k≤n)k(1≤k≤n) — the length of the permutation, the number of left bibi.
Then kk lines each contains two integer pi,xipi,xi, denoting that bpi=xibpi=xi.
输出描述:
Output one line with n integers a1,a2,⋯ana1,a2,⋯an — a possible permutation.
If no such permutation exists, output one integer -1.
示例1
输入
复制
5 2
2 2
5 4
输出
复制
1 2 5 3 4
示例2
输入
复制
10 1
1 10
输出
复制
-1
题意就是让你构造出来一个序列a，在a上从i = 1到n跑单调栈的同时使栈的大小在指定位置为特定大小。比赛的时候队友调了4h假算法QAQ
正解就是通过b数组以及题目描述，构建b数组对应位置的a数组的元素的相对关系，然后拓扑排序分配编号即可。首先需要找到一种补全b数组的方法（当然不用真的补全），而要求b[i] <= i，因此令缺失部分的b[i] = b[i - 1] + 1即可满足要求（贪心）。然后i = 1 ~ n遍历每个位置同时模拟单调栈的过程，注意和题目说的不同的是栈中存放的是一个个下标（因为本身要构造的就是a序列，同时b序列已补全，实际上存储的就是a序列的对应下标了，这样可以求出来a序列各个位置之间的数的大小关系）。遍历到一个位置时如果这个位置的b[i]没有初始值，说明在这个位置执行的是入栈操作，把i入栈，这个位置的数大于栈顶那个位置对应的数；如果b[i]有初始值，若栈的大小+1比b[i]小说明无解，如果栈的大小+1等于b[i]则把i直接入栈，这个位置的数大于栈顶那个位置对应的数，若栈的大小比b[i]大则不断弹出栈顶元素并指明栈顶元素对应位置的数大于i这个位置对应的数，最后指明i这个位置的数大于栈顶元素位置对应的数并把i入栈。这样就可以得到一系列的a[i] > a[j]这样的关系（由i指向j的有向边）构成的关系图（显然为DAG），直接跑拓扑排序分配a[i]即可。
注意如果用stl的stack实现的话需要判断栈空的情况，手动模拟的话就很方便。
#include<bits/stdc++.h>
#define N 1000005
#define M 4000005
using namespace std;
int n, k, b[N], a[N];
int head[N], ver[M], Next[M], tot = 0;
int deg[N];
void add(int x, int y) {
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void Toposort() {
queue<int> q;
int cnt = n;
for(int i = 1; i <= n; i++) {
if(!deg[i]) {
q.push(i);
}
}
while(q.size()) {
int now = q.front();
q.pop();
a[now] = cnt--;
for(int i = head[now]; i; i = Next[i]) {
int y = ver[i];
deg[y]--;
if(deg[y] == 0) {
q.push(y);
}
}
}
}
int main(){
cin >> n >> k;
for(int i = 1; i <= k; i++) {
int p, x;
cin >> p >> x;
b[p] = x;
}
stack<int> stk;//栈中存放的是一系列位置
bool ok = 1;
for(int i = 1; i <= n; i++) {
//cout << i << endl;
if(b[i]) {
if(stk.size() + 1 < b[i]) {
ok = 0;
break;
} else if(stk.size() + 1 == b[i]) {
if(i != 1) {
add(i, stk.top());//a[i]比栈顶对应位置的元素大
deg[stk.top()]++;
}
stk.push(i);
} else {
while(stk.size() + 1 > b[i] && stk.size()) {
int now = stk.top();
stk.pop();
add(now, i);
deg[i]++;
}
if(stk.size()) {
add(i, stk.top());
deg[stk.top()]++;
}
stk.push(i);
}
} else {
if(i != 1) {
add(i, stk.top());//a[i]比栈顶对应位置的元素大
deg[stk.top()]++;
}
stk.push(i);
}
}
if(!ok) {
cout << -1;
return 0;
} else {
Toposort();
for(int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
}
return 0;
}