Hướng dẫn giải của Bedao Regular Contest 07 - MTCAT


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Duyệt ngược các phần tử để cho vào mảng. Khi xét phần tử thứ ~i~, xóa hết các phần tử nhỏ hơn phần tử đang xét. Sau khi xóa hết các phần tử đó thì mảng sẽ là dãy những ngọn núi cao hơn đối với vị trí ~i~. Kết quả là phần tử có vị trí tương đương số bước nhảy, nếu số bước nhảy vượt quá kích cỡ thì in ~-1~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 +1;

int n;
int h[N], Jump[N], Result[N];
deque<int> q;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i=0; i<n; i++)
        cin >> h[i];
    for (int i=0; i<n; i++)
        cin >> Jump[i];
    for (int i=n-1; i>=0; i--){
        while (!q.empty() && h[i] >= h[q.back()])
            q.pop_back();
        int tmp = q.size() - Jump[i] + 1;
        if (tmp <= 0)
            Result[i] = -1;
        else 
            Result[i] = h[q[tmp - 1]];
        q.push_back(i);
    }
    for (int i=0; i<n; i++)
        cout << Result[i] << " ";
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.