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;
}
最后修改：2021 年 07 月 23 日 09 : 56 PM
© 允许规范转载