01/10/2018, 14:03

Thuật toán tối ưu cho bài toán đếm

Bài này em giải với T(n^3), chắc chắn là quá thời gian . Mong các anh/ chị giúp em để có 1 thuật toán tối ưu … Em cảm ơn

HK boy viết 16:17 ngày 01/10/2018

log(n^3)3log(n) rồi còn gì nữa TLE thế [spoiler]*éo[/spoiler] nào được

Lấy bất kì 2 thanh gỗ từ 2 bộ đầu tiên, rồi kiểm tra xem thanh gỗ còn lại có số đo bao nhiêu. Kiểm tra xem trong bộ thứ 3 có thanh gỗ nào có chiều dài như vậy không.

Độ phức tạp O(n^2 log n).

Tao Không Ngu. viết 16:05 ngày 01/10/2018

Hi JustTee_Phương Ly.
Bạn có thể xắp xếp một loại sau đó dùng tìm kiếm nhị phân để giản thời gian tim thanh gỗ thứ 3.

rogp10 viết 16:07 ngày 01/10/2018

Thực ra chỉ cần theta(n^2) thôi sắp xếp cả 3 mảng xong rồi giữ a, chọn b, dịch cửa sổ trong c. Tương tự cho hai lượt còn lại.

Bài liên quan
0