简答题 偏难
#22514

对于一个1到n的排列p(即1到n中每一个数在p中出现了恰好一次),令q i 为第i个位置之后第一个比p i 值更大的位置,如果不存在这样的位置,则q i = n…

对于一个1到n的排列p(即1到n中每一个数在p中出现了恰好一次),令qi为第i个位置之后第一个比pi值更大的位置,如果不存在这样的位置,则qi= n +1。举例来说,如果n = 5且p为1 5 4 2 3,则q为2 6 6 5 6。

下列程序读入了排列p,使用双向链表求解了答案。试补全程序。(第二空2分,其余 3 分)

数据范围 1 ≤ n ≤ 105。


#include <iostream>

using namespace std;

const int N = 100010;

int n;

int L[N], R[N], a[N];

int main() {

cin >> n;

for (int i = 1; i <= n; ++i) {

int x;

cin >> x;

                 (1)        ;

}

for (int i = 1; i <= n; ++i) {

R[i] =      (2)      ;

L[i] = i - 1;

}

for (int i = 1; i <= n; ++i) {

L[      (3)      ] = L[a[i]];

R[L[a[i]]] = R[      (4)      ];

}

for (int i = 1; i <= n; ++i) {

cout <<      (5)      << " ";

}

cout << endl;

return 0;

}

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p>(1)a[x] := i a[x] = i</p><p>(2)i + 1</p><p>(3)R[a[i]]</p><p>(4)a[i]</p><p>(5)R[i]</p>
这道题暂未补解析。