Xin hướng đi bài toán tính tổng của số ngày mưa ít nhất và nhiều nhất có thể

#1

Bằng cách nào đó, bạn có được một ma trận predictions , mỗi phần tử của ma trận là một mảng có dạng [s, e, k] thể hiện sẽ có đúng k ngày mưa từ ngày thứ s đến ngày thứ e.

Dù với các thông tin được đưa từ ma trận predictions bạn vẫn chưa thể đưa ra được kết luận chính xác về số lượng ngày mưa trong n ngày tới. Nhưng bạn có thể biết được số ngày mưa ít nhất và số ngày mưa nhiều nhất dựa vào các thông tin được đưa ra trong ma trận predictions. Nhiệm vụ của bạn là hãy tính tổng của số ngày mưa ít nhất và nhiều nhất có thể trong n ngày tới.

Ví dụ:

Với n = 3 và predictions = [[1,2,1],[2,3,1]] thì đầu ra của rainnyDays(n, predictions) = 3 .

  • Từ ngày 1 đến ngày 2 sẽ đúng 1 ngày mưa.
  • Từ ngày 2 đến ngày thứ 3 cũng có đúng 1 ngày mưa.

Vậy số lượng ngày mưa ít nhất là 1 ngày khi mưa vào ngày thứ 2 và số lượng ngày mưa nhiều nhất là 2 ngày khi mưa vào ngày thứ 1 và ngày thứ 3. Vậy kết quả đầu ra là 1 + 2 = 3 .

#2

s = start, e = end

Với 2 thông số trên sẽ có 1 đường thẳng kẻ trên trục Ox từ điểm s -> e.
Khi này bạn sẽ tiến hành vẽ cá đường này trên trục Ox và tính tổng overlap của nó
Giả dụ mình có 3 đoạn [1, 2, 1]; [2, 3, 1]; [2, 6, 3]; sẽ tính được tổng overlap như hình dưới
image

Để tính số ngày mưa ít nhất, với mỗi đoạn [x, y]
Ta chọn ra k điểm có tổng overlap lớn nhất trong đoạn [x, y] làm ngày mưa

Ví dụ đoạn [1, 2] có điểm 2 là có tổng overlap = 3 -> chọn 2. Vì k = 1 nên ta chỉ chọn 1 điểm
Tương tự đoạn [2, 3] -> chọn 2
Với đoạn [2, 6], sẽ chọn lần lượt các điểm 2, 3, 4
Từ các điểm được chọn ta có 2, 3, 4 -> ngày mưa ít nhất = 3

Còn ngày mưa nhiều nhất thì cứ lấy min là được.
[1, 2] -> chọn 1
[2, 3] -> chọn 3
[2, 6] -> chọn 4 5 6
-> 5 ngày mưa

Làm sao chọn nhanh max/min overlap thì bạn có thể xài interval tree

8 Likes
#3

em có 1 ví dụ thế này : n=5 ; các đoạn [ [3, 3, 1], [3, 5, 2], [2, 4, 1], [2, 4, 1], [1, 1, 1], [5, 5, 1], [4, 4, 0]]
Ở tìm min:
đoạn 1 : chọn 3
đoạn 2 : ta thấy cả 4 và 5 đều overlap=2 , vậy lúc trước vô xử lí các đoạn thì em nên kiểm tra cái nào chắc chắn có như 3 và 5 thì overlap max luôn , cái nào chắc chắn không xuất hiện thì overlap=0 ??

#4

Theo mình hiểu ý bạn là bạn muốn tính toán trước những đoạn có max overlap rùi duyệt phát như đoạn này có số 3 -> lấy max luôn ?!

Nhưng cách bạn set trước max như vậy sẽ bị hạn chế
Vì k ko phải luôn bằng 1? Khi đó có phải lưu lại số lớn t2, số lớn t3, v.v Và như vậy nhiều khi lại không tối ưu nữa.

5 Likes
#5

nhưng nếu nó chắc chắn mưa vào ngày nào đó, thì cho dù chọn max hay min thì vẫn phải có nó chứ ạ !
Ví dụ như ví dụ trên đoạn 2 tới 4 có 1 ngày mưa, mà chắc chắn ngày thứ 3 sẽ mưa , thì phải ưu tiên chọn nó rồi mới nếu còn dư ( các trường hợp >1 ngày mưa) thì xét min của những cái còn lại

#6

Bạn đừng quan tâm ngày đó mưa hay không. Với số ngày mưa ít nhất, bài toán quy về tìm các điểm có overlap lớn nhất với mỗi đoạn. Còn với ngày mưa nhiều nhất, bài toán quy về tìm các điểm có overlap ít nhất với mỗi đoạn

Như ví dụ mình chọn ngày 3 là ngày mưa trong đoạn [2, 6]. Mặc dù 3 được biết là không mưa ở đoạn [2, 3]

Vì đề yêu cầu tính toán nên mình sẽ bỏ qua những ngày mưa đi để giảm bớt tính toán không cần (như xem ngày nào không mưa có mưa để loại trừ). Trừ khi nào đề kêu in ra những ngày có mưa thì mình khi đó mới cần quan tâm nè.

5 Likes
#8

có những trường hợp nó có đoạn [3,3,1] hoặc [5,5,0]
thì ta biết kiểu gì nó cũng sẽ có mưa hoặc k mưa chứ ạ ??
những trường hợp nó như thế này e mới quy nó về max ( 1 số cố định )
khi duyệt max min thì trong đoạn nào đó check xem = số max cố định ở trên thì auto chọn
Giả sử ta đang tìm max đoạn [2,5,2] mà ta có [3,3,1] và [5,5,1] rồi thằng 2,4 cho dù như thế nào cũng đâu ảnh hưởng ạ?

#9

Vậy là như mình nói. Là bạn muốn lưu max/min lại xong rồi lấy ra thôi đúng không? Như vậy thì đúng là sẽ tối ưu với trường hợp k = 1 :+1:

6 Likes
#10

Giải thuật là như này:
Để tìm min thì ta ưu tiên bỏ các ngày mưa vào những ô thuộc nhiều đoạn nhất, tạm gọi là d[i] là số đoạn mà ô i thuộc vào (vd trong đề thì ô 2 thuộc 2 đoạn, d[i] = 2). (việc tìm những ô thuộc nhiều đoạn nhất thì có thẻ dùng mảng công dồn, giới hạn cao hơn có thể sort + nén mảng).
Rồi với mỗi bước, xét mỗi ô, ưu tiên những ô có d[i] lớn nhất. với những ô đó thì lấy hết số ngày bỏ vào.

Tìm max thì duyệt qua các đoạn, sau đó ưu tiên xếp ngày mưa vào những ô có d[i] nhỏ nhất trong đoạn đó, sau khi xếp xong thì cho d[i] của những ô đã được xếp = vô cùng để khi xử lí đoạn tiếp theo không bị xếp trùng vào.

3 Likes
#11

8, [[1, 2, 1], [3, 7, 2], [5, 7, 1], [8, 8, 0], [1, 6, 3], [7, 8, 0], [2, 4, 2], [7, 7, 0], [4, 8, 2], [5, 6, 1], [2, 3, 1]]
Em có ví dụ như thế này ra output là 6 . Giải thích mãi không được ạ , ai giúp em với

#12

thằng 5 và 6 đều xuất hiện 5 lần, trong khi thằng 4 chỉ xuất hiện 4 lần ( ở đoạn [3,7,2] thì theo max là 5 và 6 )
nhưng khi chọn min thì ta phải chọn 2 4 5

#13

:sneezing_face::sneezing_face::sneezing_face::sneezing_face:

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