Trinh thám


Submit solution

Points: 4
Time limit: 1.0s
Memory limit: 977M

Author:
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

Amas là một sinh viên mới vào học tại ĐHGVTVT năm thứ nhất. Kết thúc học kỳ 1, Amas được tham gia một học kỳ quân sự. Hôm nay, lớp học của Amas được chia làm 2 phía chiến trường và tổ chức tập trận, Amas tham gia bên phía quân xanh có nhiệm vụ đi trinh thám quân đỏ huấn luyện. Amas leo lên một quả đồi và sử dụng ống nhòm để quan sát thì phát hiện ra quân đỏ đang dàn hàng ngang để tập luyện, khổ nỗi ống nhòm nhỏ nên mỗi khung nhìn chỉ quan sát được một số lính liên tiếp của quân đỏ. Nhiệm vụ trinh thám lần này là tìm ra chiều cao cao nhất của đối phương, để làm được điều đó rất khó nên phải quan sát dần dần lần lượt từ đầu đến cuối của hàng bằng cách dịch khung nhìn lần lượt mỗi lần tịnh tiến lên một đơn vị.

Bài toán đặt ra với Amas là với n quân đỏ có chiều lượt là \(a_1, a_2...a_n\), khung nhìn có khoảng rộng là \(1<=k<=n\). Khi dịch khung nhìn lần lượt từ đầu đến cuối thì với từng vị trí khung nhìn phải tìm ra chiều cao của quân đỏ cao nhất trong khung nhìn đó

Input

Dòng đầu chứa 2 số n là số quân đỏ \((1<= n <=10^5)\) và k là khung nhìn của ống nhòm \((1<=k<=n)\) (số quân đỏ tối đa mà một lần ống nhòm quan sát được)

Dòng thứ 2 chứa n số nguyên là chiều cao của quân đỏ theo đơn vị chiều cao \((1<= a_i <= 10^4)\)

Output

Kết quả đầu ra gồm n-k+1 số nguyên là chiều cao của quân đỏ cao nhất trong từng khung nhìn

Ví dụ

8 3
4 7 2 5 6 3 9 1

Output

7 7 6 6 9 9

Giải thích Lần lượt khung nhìn duyệt qua 3 phần tử một tìm \(max(4,7,2), max(7,2,5), max(2,5,6), max(5,6,3), max(6,3,9), max(3,9,1)\)

tichpx

Comments


  • 1
    LãoTam  commented on Oct. 28, 2021, 12:48 p.m.

    [user:^_^]Tham Khảo

    #include<bits/stdc++.h>
    #include<iostream>
    using namespace std;
    int main() {
        int n,k,x;
        list<int> L; //luu vi tri theo gia tri giam dan dang xet
        cin>>n>>k;
        vector<int> a(n+5);
        for(int i=1; i<=n; i++)
            cin>>a[i];
        for(int i=1; i<k; i++) {
            while(L.size()>0 && a[L.back()]<a[i]) L.pop_back();
            L.push_back(i);
        }
        for(int i=k; i<=n; i++) {
            while(L.size()>0 && a[L.back()]<a[i]) L.pop_back();
            L.push_back(i);
            while(i-L.front()>=k)
                L.pop_front();
            cout<<a[L.front()]<<" ";
        }
    }

  • 2
    TICHPX  commented on Sept. 17, 2020, 10:11 a.m. edited
    #Python dùng PriorityQueue mà bị TLE
    from queue import PriorityQueue
    class elem:
        def __init__(self,v=0,g=0): self.vitri,self.giatri = v,g
        def __lt__(self, other): return self.giatri>other.giatri
    
    if __name__ == '__main__':
        Q=PriorityQueue()
        n,k=map(int,input().split())
        a=list(map(int,input().split()))
        for i,x in enumerate(a):
            Q.put(elem(i,x))
            if i>=k-1 :
                while i-Q.queue[0].vitri>=k: Q.get()
                print(Q.queue[0].giatri,end = ' ')

  • 1
    TICHPX  commented on June 15, 2020, 8:34 a.m.

    Có vẻ bài này test yếu, ta có nâng cấp lên \(n = 10^6\) không nhỉ? Duyệt 2 vòng lặp mà cũng AC


    • 1
      Giang_CNTT3_K60  commented on June 15, 2020, 11:27 a.m.

      hợp lý thầy ạ :))