2021牛客暑期多校训练营2 K题 Stack
题目描述
ZYT had a magic permutation $a_1,a_2,\cdots, a_n$, and he constructed a sequence $b_1,b_2,\cdots b_n$ 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 size
But he somehow forgot the permutation ${a}$, and only got some ${k}$ elements of $b_i$.
Construct a permutation ${a}$ satisfying these $b_i$, or determine no such permutation exists.
Here a permutation refers to a sequence that contains all integers from ${1}$ to ${n}$ exactly once.
输入描述:
The first line contains two integers ${n},{k} (1\leq k\leq n)$— the length of the permutation, the number of left $b_i$.
Then ${k}$ lines each contains two integer $p_i,x_i$, denoting that $b_{p_i}=x_i$.
输出描述:
Output one line with n integers $a_1,a_2,\cdots a_n$ — 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
备注:
It's guaranteed that $n\leq 10^6,1\leq p_i,x_i\leq n$, and $\forall i\ne j,p_i\ne p_j$.
题解
这一题是一个构造题,可以纯粹构造来解决,也可以构造+数据结构+二分,题解采用第二种方法。这一题大致意思是给你一个$n$,然后给你$k$个$b[i](k<=n)$的值,然后让你构造出一个$a$数组满足题目的伪代码需求(一个单调栈,$ b[i]$代表单调栈目前的大小,$a[i]$是被放入单调栈中的元素)。
首先考虑构造$b$数组。显然对于每一个$ b[i]$,必须满足 $b[i] \leq i$且$b[0]=1$,那么对于未给出数值的 $b[i]$,令 $b[i] = b[i - 1] + 1$,这样构造能够满足$b[i] \leq i$的条件,随后只需要从后往前构造即可。这样构造出的数组$b$一定满足:$b[i]<=i$且$b[0]=1$.
然后难点是求$a$数组。我们可以从后往前构造,让每一个$a[i]$ 前面都可以有$b[i]$个没有使用且比它小的数。那么如何找到这样的$a[i]$呢?我们可以使用树状数组记录已经使用了多少个数,然后使用二分来寻找满足构造条件且最小的$a[i]$的值。这样,我们得到的$a[i]$数组一定是一个满足构造条件的数组。
为什么是最小的$a[i]$:这样可以保证不会有数字被浪费,使$n$个数字都被使用,也就不会出现重复数字和超过$n$的数字。
代码
代码如下:
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;
int n, k;
int a[maxn];
int b[maxn];
int tree[maxn];
int num[maxn];
int lowbit(int x) { return x & (-x); }
void add(int x,int k) {
for (int i = x; i <= n; i += lowbit(i)) {
tree[i] += k;
}
}
int getsum(int x) {
int sum = 0;
for (int i = x; i >= 1; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}
int mid_query(int l, int r, int k) {
while (r - l > 1) {
int mid = (l + r) >> 1;
int num = getsum(mid);
if (num >= k)
r = mid;
else
l = mid;
}
return r;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= k; i++) {
int l, r;
cin >> l >> r;
b[l] = r;
}
int flag = 0;
for (int i = 1; i <= n; i++) {
add(i, 1);
if (!b[i]) {
b[i] = b[i - 1] + 1;
}
if (b[i] - b[i - 1] > 1) flag = 1;
}
if (flag == 1) {
cout << -1 << endl;
return 0;
}
for (int i = n; i >= 1; i--) {
a[i] = mid_query(0, n + 1, b[i]);
add(a[i], -1);
}
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
return 0;
}