Chào đón tân sinh viên K59

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 977M
Authors:
TICHPX, ndh96coder
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Nhân dịp chào đón các tân sinh viên K59 Đại học Giao thông vận tải, Nhà trường tổ chức các trò chơi trí tuệ cho các tân sinh viên có một tinh thần thật thoải mái trước khi bước vào năm học. Trò chơi thú vị này có luật chơi như sau:

Có tất cả n sinh viên tham dự, xếp thành một hàng và mỗi bạn được đánh số từ 0 đến n - 1. Sau khi chỉ định bất kỳ bạn nào, bạn đó sẽ phải chỉ ra chỉ số của bạn đứng gần mình nhất mà có chiều cao cao hơn mình, Nếu có nhiều chỉ số cùng thỏa mãn thì lấy chỉ số bé hơn, nếu không có ai cao hơn thì chỉ số đó sẽ là -1.

Để trò chơi diễn ra thuận lợi và công bằng, Thầy TichPX giao cho đội tuyển Olympic tin học UTC viết một chương trình nhập vào một dãy số nguyên a cho biết chiều cao của sinh viên ở từng chỉ số, và in ra dãy số nguyên khác thể hiện chỉ số cần tìm ở mỗi vị trí trong dãy ban đầu.

Ví dụ: a = [1, 4, 2, 1, 7, 6] thì output sẽ là: b = [1, 4, 1, 2, -1, 4]

  • Với a[0] = 1 thì người cao hơn gần nhất là a[1] = 4 tại chỉ số là 1.
  • Với a[1] = 4 thì tương ứng chiều cao gần nhất là a[4] = 7 có chỉ số là 4.
  • Với a[2] = 2 thì người cao hơn gần nhất là a[1] = 4 tại chỉ số là 1.
  • Với a[3] = 1 thì người cao hơn gần nhất là a[2] = 2 tại chỉ số là 2.
  • Với a[4] = 7 thì không có ai cao hơn nên chỉ số là -1.
  • Với a[5] = 6 thì người cao hơn gần nhất là a[4] = 7 có chỉ số là 4.

Input:

Dòng đầu tiên là n thể hiên số sinh viên \((1 <= n <= 4.10^4)\)

Dòng thứ 2 bao gồm n số nguyên thể hiện chiều cao của n sinh viên. số thứ i thể hiên chiều cao của sinh viên thứ i \(( 0 <= i < n)\)  

Output:

Dòng duy nhất in ra n số nguyên. Số thứ i tương ứng là chỉ số của sinh viên gần nhất cao hơn sinh viên thứ i trong dãy đã cho.

Ví dụ

Input:

6
1 4 2 1 7 6

Output:

1 4 1 2 -1 4

Chú ý

Nếu có nhiều chỉ số cùng thỏa mãn thì lấy chỉ số bé hơn, nếu không có ai cao hơn thì chỉ số đó sẽ là -1.

tichpx

Comments


  • 0
    hairep2005  commented on Nov. 22, 2024, 2:40 p.m.

    Mọi người nhìn giúp em bài này xem còn sót trường hợp nào với ạ, đầu tiên em tìm thằng lớn hơn nằm bên phải trước , xog em tìm thằng lớn hơn bên trái

    include<bits/stdc++.h>

    using namespace std;

    long long a[100000] ;

    int chiso[100000] ;

    void nextGreaterElement(int n){

    stack<long long> st; 

st.push(0);

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

    while(!st.empty() and a[i] > a[st.top()]){

        chiso[st.top()] = i ; 

        st.pop() ; 
    }

    st.push(i) ; 

}

while(!st.empty()){

    chiso[st.top()] =1e9 ; 

    st.pop() ; 

}

    }

    void backGreaterElement(int n){

    stack<long long> st; 

st.push(n-1) ; 

for(int i=n-2;i>=0;i--){

    while(!st.empty() and a[i]>a[st.top()]){

        chiso[st.top()] =min(chiso[st.top()],i) ; 

        st.pop() ; 

    }

    st.push(i) ; 

}

while(!st.empty()){

    if(chiso[st.top()] == 1e9){

        chiso[st.top()] =-1 ;

    }

    st.pop() ; 

}

    } int main(){

    int n  ; cin>> n ; 

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

    cin>>a[i] ; 

}

nextGreaterElement(n) ; 

backGreaterElement(n) ; 

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

    cout<<chiso[i]<<" " ; 

}

    }


  • -1
    NguyễnTiếnTàiCNTT3K61  commented on Sept. 28, 2022, 9:45 a.m. ← edited 
    import math
import queue
n=int(input())
a=[math.inf]
a+=list(map(int,input().split()))
S = queue.LifoQueue()
L=[]
R=[]

for i in range(n+1):
   if(i==0): S.put(i)
   else:
       while S.empty()==False:
           t =S.get()
           if(a[t] > a[i]):
               S.put(t)
               L.append(t)
               S.put(i)
               break

while S.empty()==False:
    S.get()

for i in range(n+1):
   if(i==0): S.put(i)
   else:
       while S.empty()==False:
           t =S.get()
           if(a[t]>a[n+1-i]):
               S.put(t)
               R.append(t)
               S.put(n+1-i)
               break
R.reverse()

result=[]
for i in range(n):
    if(L[i]==R[i]==0):
        result.append(-1)
    elif L[i]==0: result.append(R[i]-1)
    elif R[i]==0: result.append(L[i]-1)
    elif(-L[i]+i+1 <= R[i]-i-1):
        result.append(L[i]-1)
    else: result.append(R[i]-1)
s=""
for i in result:
    s+=str(i)+" "
print(s)

  • 1
    I_love_NguyenLinh  commented on Sept. 17, 2018, 6:35 a.m.

    tương tự :D thế mà lúc thi cà cuống nghĩ đúng r lại thôi :D http://vnoi.info/wiki/algo/data-structures/deque-min-max