In ra mảng gồm các phần tử nhỏ thứ i/4

LittleABC · 14/11/16

Cho 1 dãy A gồm N số, N < 10000000. In ra mảng B gồm các phần tử B là phần tử nhỏ thứ ceiling(i/4) trong dãy từ A[0] tới A[i - 1]. Ví dụ nếu A là 5, 3, 4, 6, 7, 2, 8, 2 thì B là 5, 3, 3, 3, 4, 3, 3, 2.

tengiday · 14/11/16

Bài này sẽ dùng 2 loại heap: min vả max heap. Tuy nhiên đề bài và ví dụ hình như bị lệch index rồi. Bạn hỏi thầy lại cho kỹ nhé, tốt nhất là làm rõ ví dụ ra.

LittleABC · 15/11/16

Mình ghi nhầm: Cho 1 dãy A gồm N số, N < 10000000. In ra mảng B gồm các phần tử B là phần tử nhỏ thứ floor(i/4) trong dãy từ A[0] tới A. Ví dụ nếu A là 5, 3, 4, 6, 7, 2, 8, 2 thì B là 5, 3, 3, 3, 4, 3, 3, 2. Cám ơn bạn.

tengiday · 15/11/16

Như mình đã nói, bạn dùng 2 heap: max và min. Max heap chứa 25% của mảng A[0..i], còn min heap chứa 75% của mảng A[0..i].
- Nếu A >= maxHeap.top thì đưa A vào minHeap.
- Nếu A < maxHeap.top thì chuyển maxHeap.top vào minHeap, sau đó đưa A vào maxHeap.
- Cuối cùng lưu ý trường hợp maxHeap.size < i/4 thì phải chuyển minHeap.top vào maxHeap.
- Tại mỗi i, sau khi thực hiện các bước trên thì B = maxHeap.top.
Thuật toán có độ phức tạp O(n log n). Với N = 10000000 thì cái này vừa đúng thời gian.

In ra mảng gồm các phần tử nhỏ thứ i/4

tengiday

Happy life

LittleABC

tengiday

Happy life

Bài viết mới nhất

Thống kê

Bài viết được quan tâm nhiều