Gợi ý bài tính số phần tử liên tiếp dài nhất có trọng số không quá k

#1

Cho dãy a có n phần tử
Yêu cầu: Với mỗi giá trị k, hãy tìm ra dãy con liên tiếp mà mỗi phần tử trong dãy đó có giá trị <= k.
Input

  • Dòng đầu tiên chứa hai số nguyên dương n và Q (1 <= n, Q <= 10^5).
  • Dòng thứ hai chứa n số nguyên dương a[1], a[2],... a[n] (1 <= a[i] <= 10^9) là giá trị của các phần tử.
  • Q dòng tiếp theo, mỗi dòng chứa 1 số nguyên k (1 <= k <= 10^9).

Kết quả: Mỗi dòng ghi 1 số nguyên dương tương ứng là kết quả được tính theo dữ liệu vào (có Q dòng).
Ràng buộc:

  • Có 80% số test tương ứng với: Q, n <= 10^3
  • 20% số test còn lại không có ràng buộc gì thêm.

Ví dụ:

Input:
6 3
4 2 3 5 8 1
4
2

Output:
3
6
1

Giải thích:

  • Với k = 4, nhận thấy có 2 dãy thỏa mãn đó là 4 2 3 và 1 đều có giá trị mỗi phần tử <= k, nhưng do 4 2 3 có số lượng phần tử nhiều hơn nên được chọn -> Ghi số 3.
  • Với k = 12, mọi phần tử của của dãy a đều thỏa mãn <= k nên được chọn cả dãy -> Ghi số 6
  • Với k = 2, Có 2 dãy thỏa mãn và có cùng độ dài: 2 và 1 -> Ghi số 1

Đề lớp 10 tỉnh em đây, mà không biết làm subtask cuối T_T. Nhờ mọi người giúp subtask cuối với ạ, em cảm ơn mọi người

#2

Trước hết, bạn nên show code hiện tại của bạn để mọi người biết bạn đang bị vướng ở đâu, và xem thử có thể tối ưu được hay không.

2 Likes
#3

Mình có thử segment tree (max) nhưng lỡ 1 đoạn giữa 2 nhánh thì chịu.

2 Likes
#4

mình đang mắc ở subtask cuối, tức là không có ý tưởng code bạn ạ, còn subtask đầu thì mình làm được OK rồi.

#5

mình cũng có nghĩ đến cách này, nhưng mà khó để lấy đoạn liên tiếp

ví dụ với cái này là mình lấy cả 4 2 3 1 luôn chứ không phải 4 2 3 .
Haizz @@

#6

Ý mình ở đây là code hiện tại giải sub đầu tiên ấy bạn. Nếu bạn đang giải với O(n^3) thì có thể chỉ cần tìm O(n^2) là được, không cần nhất thiết phải O(NlogN), hoặc là biết đâu code hiện tại của bạn bị dư…

2 Likes
#7

Đầu tiên bạn để ý

dãy con liên tiếp mà mỗi phần tử trong dãy đó có giá trị <= k (1)

  • (1) tương đương với max của dãy con đó <= k.

  • Mặt khác, từ (1) suy ra min của dãy con đó <= k.

Thứ 2, nếu 1 dãy con a[l], a[l+1],... a[r] là 1 dãy con thoả mãn (1), thì a[l+1],... a[r] cũng thoả mãn (1).

Bạn có thể áp dụng RMQ (range minimum/maximum query) cho bài này. Bạn tự tìm hiểu thêm, do mình học lâu quá quên rồi nên có thể vài chỗ đặt chỉ số không đúng.

Gọi l là chỉ số đầu, ta cần tìm r tương ứng là chỉ số cuối của dãy con thoả mãn (1). Lưu ý a[l-1] (nếu có) > k và a[r+1] (nếu có) > k.

Xét a[l] <= k. Tư tưởng chính là với mỗi l, tìm r xa nhất có thể mà max(a[l..r]) <= k. Chỗ này hoàn toàn dùng RMQ trong O(log n).

const LOG2_N = 16; // floor(log2(max_n)) = floor(log2(1e5))

int max_lr = a[l], r = l; // khởi tạo
for (int i = LOG2_N; i >= 0 && r + (1 << i) < n; i--) {
    // nhảy bước r thêm 1 << i
    if (rmq_max[r][i] <= k) {
        // có thể kéo dài dãy thêm 1 đoạn 1 << i nữa
        r += (1 << i) - 1;
    }
    // nếu không thì dãy sẽ kéo dài ít hơn
}

Sau khi tìm được r xa nhất thoả mãn, giá trị l tiếp theo cần xét tối thiểu là r + 1.

Độ phức tạp tối đa của thuật toán hơi sơ khai này là O(n log n), trường hợp xui xẻo nhất là phải duyệt cả mảng để tìm chỉ số l đầu tiên thoả mãn a[l] <= k.

Để tối ưu, bạn có thể tìm cách nhảy nhanh l trong O(log n) dùng rmq_min, tuy nhiên hơi phức tạp. Trước mắt bạn cứ cài được giải thuật trên đã.

1 Like
#8

Mình làm được O(n^2) rồi bạn, cố suy nghĩ cái O(NlogN) mà không ra. :((

#9

Ok cảm ơn anh nhé, trông cấu trúc dữ liệu này hơi dài, chắc phải học lâu lâu rồi quay lại làm cái này được

#10

Bài này dường như không cần đi xa vậy, việc tìm mảng max <=k có thể tìm trong O(N) nếu làm như vầy mà:

Bài toán này chỉ có Q hơi to, nên tính ra độ phức tạp cả bài là Q*O(N) \approx O(N^2)

2 Likes
#11

Trước hết, em xin cảm ơn @noname00, @rogp10, @Stanley00 vì đã góp phần giúp em bài tập này. Sau 1 thời gian thì em đã có 1 thuật toán để giải quyết bài này mà không cần quá nặng về cài đặt các cấu trúc dữ liệu , mọi người xem và nhận xét nếu thiếu sót.

Theo nhiệm vụ bài ra thì ta cần phải tìm được dãy con có các phần tử liên tiếp mà mỗi phần tử trong dãy đó đều <= k
Giả sử gọi phần tử mà ta đang xét là a[i]

  • Vậy thì để dễ dàng cho việc tìm số phần tử thỏa mãn đề bài thì trước hết ta nên xác định được đoạn a[l] ... a[r] mà mọi phần tử trong đoạn [l; r] đều <= a[i] (l <= i <= r).
Code 
int l[N], r[N];
        // Tìm phần tử đầu tiên nằm ở phía trên trái a[i] và > a[i]
	for (int i = 1; i <= n; i++) {
		l[i] = i - 1;
		while(l[i] > 0 && a[l[i]].st <= a[i].st)
			l[i] = l[l[i]];
 
	}
        // Tìm phần tử đầu tiên nằm ở phía trên phải a[i] và > a[i]
	for (int i = n; i >= 1; i--) {
		r[i] = i + 1;
		while (r[i] <= n && a[r[i]].st <= a[i].st)
			r[i] = r[r[i]];
	}
        // Lưu số lượng phần tử liên tiếp thỏa mãn
	for (int i = 1; i <= n; i++)
		a[i].nd = r[i] - l[i] - 1;
  • Sau đó sắp xếp lại các phần tử mảng a theo thứ tự tăng dần, ở đây em dùng pair để khi sắp xếp lại mảng a thì đưa theo số phần tử liên tiếp mà <= a[i] .
  • Với mỗi truy vấn vấn k, thì ta sẽ sử dụng phương pháp chặt nhị phân để tìm ra phần tử a[i] đầu tiên mà > k. Nhưng do trong dãy a sẽ có nhiều đoạn con có các phần tử liên tiếp < k nên kết quả cần ghi ra sẽ là max(a[1].nd ... a[k-1].nd)

Code cả bài hoàn chỉnh: Here.

Đây là lần đầu em viết về lời giải nên có thể có rất nhiều sai sót, nếu ai đọc mà cảm thấy khó hiểu thì cứ phản hồi, em sẽ sửa chữa. Em cảm ơn!

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?