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

Bài liên quan
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
log(n^3)
là3log(n)
rồi còn gì nữa TLE thế [spoiler]*éo[/spoiler] nào đượcLấ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).
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.
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.