Thắc mắc bài toán chọn hoa

#1

hoacutlon.jpg4192×3104 1.81 MB

Cô giáo em vừa cho bài như trên.
Em có ý tưởng là cho hết độ đẹp vào 1 mảng, sắp xếp mảng tăng dần rồi lấy phần tử cuối trừ đầu, đó là độ chênh lệch lớn nhất về “mức độ đẹp”.
Song để tìm số cách chọn thì duyệt mảng từ phần tử thứ 2, cộng độ chêch lệch max ở trên và xem nó có bé hơn phần tử cuối không, nếu có thì tăng đếm lên1. Nhưng mà như thế thì còn gọi gì là cách chọn khác nhau gì nữa, luôn luôn chỉ có 1 cách chọn thì nguuwòi ta còn bắt đém cách chọn làm gì :joy: , hay tại em ngu. Mong các cao nhân chỉ giáo.

#2

Nố nô nồ.

6
1 1 1 5 5 5

ra
4 3

4 9

nhé.

#3

Nhưng mà người ta cho 2 cách chọn khác nhau nếu có ít nhất 1 bông hoa xuất hiện trong cách thứ 1 và không trong cách thứ 2, của anh lặp rồi :joy:

#4

Đâu nào. Bạn đọc kĩ test case của mình nhé. Có khi mình còn đếm thiếu ấy chứ.

a[1] - a[4]
a[1] - a[5]
a[1] - a[6]
a[2] - a[4]
a[2] - a[5]
a[2] - a[6]
a[3] - a[4]
a[3] - a[5]
a[3] - a[6]

-> 9 cách. Mình sửa test case đây.

P/s: Ý tưởng của bạn đúng rồi, chỉ thêm 1 chút nữa là AC cả bài.

#5

đúng rồi, em cứ nghĩ là độ đẹp của bông hoa phải khcá nhau. Đúng ra là phải các bông hoa khgác nhau. Ema cảm ơn anh.

1 Like
#6

Không nhầm đây là đề thi tỉnh Hải Dương =)))

2 Likes
#7

Gợi ý: [spoiler]Lấy hiệu hai phần tử liên tiếp.[/spoiler] O(N) time và O(1) mem. @nts311

(theo đề thì không cần, nhưng thêm điều kiện thì chỉ mỗi cách này đúng)

1 Like
#8

Không chắc là lấy hiệu 2 phần tử đâu bác. Đề bài có bảo thế đâu.

#9

Nếu 2 test cuối cho N lên tận 2*10^5 thì lâu thật, có khi đơ luôn ấy chứ.

1 Like
#10

2*10^5 làm O(N) là đẹp. O(N^2) mới chết. Thuật của bạn là O(N log N) (có sort) thì chạy ù cái là xong ấy mà. 1s máy tính thực hiện khoảng 10^8 phép tính (đối với máy cùi)

1 Like
#11

O(NlogN) với sort thì vừa đủ rồi, thực ra có thể chạy với O(4N) và chú ý trường hợp tất cả bằng nhau. Mình nghi có test đấy là test chết =))

1 Like
#12

Trường hợp tất cả bằng nhau -> in ra 0 n * (n+1) / 2. Khỏi xoắn nhé.

1 Like
#13

vừa em cho chạy máy ở nhà thì mất có 0.3(s) thôi

#14

n*(n-1) / 2 chứ, bảo bạn kia để ý test chết thôi.

1 Like
#15

“Chênh lệch” là trừ rồi còn gì.

Mà phải vậy mới là gợi ý chứ :slight_smile: giải hộ sao còn là gợi ý nữa.

1 Like
#16

tức là mình lấy hiệu từng cặp số để tìm dộ chênh lệch lớn nhất ạ?

#17

Thôi bỏ qua đi, nhầm bài :smiley: lấy max trừ min thôi. Xong rồi duyệt lại đếm số.

Ngoài ra cũng có bài tương tự nhưng có thêm điều kiện, không max min được (để ngược max min là bí). Trừ liên tiếp mới được.

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