题库 信息学奥赛题库 题目列表 对于一个1到n的排列p(即1到n中每一个数在p中出现了恰...
填空题

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

举例来说,如果n=5p1 5 4 2 3,则q2 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; 
}
题目信息
完善程序 初赛 2018年
-
正确率
0
评论
248
点击