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

luôn luôn chỉ có 1 cách chọn

Nố nô nồ.

6
1 1 1 5 5 5

ra
4 3

4 9

nhé.

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

Đâ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.

đú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.

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

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)

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

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ứ.

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)

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 =))

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

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

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

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

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

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

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 ạ?

Thôi bỏ qua đi, nhầm bài 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.