Gợi ý bài tập đếm số lượng phần tử lớn nhất trong dãy con liên tiếp k phần tử

[Quoc_Bao_Nguyen1 (Quốc Bảo Nguyễn)]

Mn giúp em ý bài này với ạ, nếu số lớn nhất đã được đếm rồi thầy không đếm nữa phải không ạ

[nguy4nkjn (Nguyen Khasnh)]

Ví dụ trên mình hiểu là có 2 số lớn nhất trong dãy con k phần tử là 4 và 6 vì 4 có trong dãy con (1-4) (2-1) còn 6 có trong dãy con (3-6).

[anonymous282]

Phân tích bài này một xíu:

• Cho dãy N phần từ, đánh số từ 1 đến N cần tìm tất cả dãy con liên tiếp có K phần từ. Rồi tìm số lớn nhất của các dãy con này.
• Vì dãy con là liên tiếp, nên dãy con đầu tiên sẽ gồm các phần tử từ 1 đến K, dãy tiếp theo là từ 2 đến K+1… dãy con cuối cùng là từ N-K+1 đến N => có tất cả N-K+1 dãy con. Sẽ có 2 trường hợp:
  • Nếu số lớn nhất đã đếm rồi được đếm lại => mỗi dãy con sẽ luôn có 1 số lớn nhất => đáp án bài toán là N-K+1
  • Nếu số lớn nhất đã đếm rồi không phải đếm nữa => tìm và đánh dấu phần từ lớn nhất rồi duyệt lại toàn dãy để đếm
• Vậy, theo bạn @Quoc_Bao_Nguyen1 thì trường hợp nào sẽ hợp lý hơn?

[Quoc_Bao_Nguyen1 (Quốc Bảo Nguyễn)]

Trường hợp 2 ạ, với mình dùng cách này ổn k b
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n, k; cin >> n >> k;
int a[n];
int cnt = 0, max1 = -1e9;
set s;
for(int i=0; i<n; i++) cin >> a[i];

for(int i=0; i<=n-k; i++){
    max1 = -1e18;
    for(int j=0;j<k;j++){
        max1 = max(max1,a[i+j]);
    }
    s.insert(max1);
}
cout << s.size();
return 0;

}

[anonymous282]

Không rõ là ổn không nhưng bạn thử test với input này xem:

6 2
1 2 1 2 1 2

[rogp10]

Bài này mình sẽ dùng max-heap.

[Quoc_Bao_Nguyen1 (Quốc Bảo Nguyễn)]

Nó ra như này ạ

[anonymous282]

Hmm… Hình như là bạn học hơi thụ động thì phải.
Bạn thấy output này đúng hay sai?
Tại sao đáp án trong code lại là 1?
Bạn tự giải tay thì ra đáp án là bao nhiêu?
vân vân và mây mây…