Solutions of Birthday

Select solution language

hvnamyd Created at 0 likes

Hàm kiểm tra của bài này để kiểm tra xem một số thực $x$ có thể là phần bánh mỗi bạn được nhận không (nghĩa là khi chia mỗi bánh làm $x$ phần thì có đủ cho $k$ bạn hay không). Chi tiết hàm kiểm tra như sau: Với mỗi cái bánh diện tích $a[i]$ thì chia $a[i]$ cho $x$ lấy phần nguyên thì thương là số bạn có thể chia được với cái bánh $a[i]$ đấy. Tính tổng các thương này lại rồi so sánh tổng đó với $k$, nếu $>=k$ thì chia đủ. Sau đó thực hiện tìm kiếm nhị phân kết quả trên số thực với hàm tìm kiếm ở trên. Lưu ý: vì là số thực nên không lặp bằng while đầu <= cuối mà dùng vòng for để lặp khoảng 100 lần là vừa đủ chính xác. Độ phức tạp của thuật toán này là O(100n).