Bình luận

• 
  

  0

  

  minhkochamhoc  đã bình luận lúc 22, Tháng 11, 2025, 0:03

  bài y hệt : https://oj.vnoi.info/problem/fct025_dance

• 
  

  2

  

  minhkochamhoc  đã bình luận lúc 21, Tháng 11, 2025, 14:37

  solve:

  nhận xét :

  • đề yêu cầu đếm số cách chọn ra 1 cặp nam nữ sao cho chiều cao của bạn nam lớn hơn hoặc bằng chiều cao bạn nữ và nhỏ hơn hoặc bằng chiều cao bạn nữ + k
  • hay ta có thể biểu diễn như sau : gọi HFemale là chiều cao bạn nữ , HMale là chiều cao bạn nam thì
  • HFemale <= HMale <= HFemale + k
  • từ đó ta thấy rằng với mỗi bạn nữ ta cần đếm xem có bao nhiêu bạn nam có chiều cao thỏa mãn biểu thức trên
  • để giải quyết việc đếm nhanh số lượng ta phần tử trong 1 khoảng ta có thể nghĩ tới chặt nhị phân hoặc tổng cộng dồn

  áp dụng chia nhị phân :

  • gọi ans là số cách chọn ra 1 cặp nam nữ hợp lệ
  • đầu tiên ta thấy ta cần tách những bạn nam và bạn nữ trong mảng ban đầu ra làm 2 mảng là Male và Female
  • sau đó vì để thỏa mãn tính chất của chặt nhị phân ta cần sắp xếp lại mảng Male
  • duyệt mảng Female , với mỗi bạn nữ thứ i có chiều cao HFemale ta sử dụng tìm kiếm nhị phân trong mảng Male để tìm
  • vị trí l là vị trí bạn nam đầu tiên có chiều cao HMale >= HFemale mà ta đang xét
  • vị trí r là vị trí bạn nam cuối cùng thỏa mãn HMale <= HFemale + k
  • ta thấy rằng vì đây là 2 cận đầu và cuối thỏa mãn điều kiện của ta cho nên tất cả các bn nam nằm trong khoảng [l,r] đều thỏa mãn cho nên bạn nữ hiện tại có thể ghép với bất kỳ bạn nào trong r - l + 1 bạn này
  • => ans += r - l + 1
  • code của tớ : binary search

  áp dụng tổng cộng dồn :

  • gọi ans là số cách chọn ra 1 cặp nam nữ hợp lệ
  • ta định nghĩa mảng Male[i] , Female[i] trả về số bạn nam / bạn nữ có chiều cao i
  • bước đầu tiên ta sẽ duyệt lại mảng ban đầu đề bài cho để đếm phân phối các bạn nam / nữ có chiều cao i
  • tiếp theo ta xây dựng tổng cộng dồn trên mảng Male
  • sau đó ta duyệt qua mảng Female , với các bạn nữ hiện tại đang xét có chiều cao i
  • ta có thể sử dụng tính chất mảng tổng dồn để để đếm nhanh xem có bao nhiêu bạn nam thỏa mãn điều kiện bằng cách lấy : Male[i + k] - Male[i - 1]
  • từ đó ta thấy rằng với 1 bạn nữ mang chiều cao i thì có Male[i + k] - Male[i - 1] bạn nam thỏa mãn thì bây giờ với Female[i] bạn nữ ta sẽ có Female[i] * (Male[i + k] - Male[i - 1])
  • => ans += Female[i] * (Male[i + k] - Male[i - 1])
  • chú ý : xét riêng trường hợp các bạn nữ có chiều cao là 0 do nếu tính chung ta sẽ truy cập vào phần tử Male[0 - 1] gây ra lỗi RTE do mảng ko có chỉ số âm nhưng các bạn nữ có chiều cao 0 thì vẫn được tính vào kết quả
  • đây là code của tớ : prefix sum

• 
  

  0

  

  al042548  đã bình luận lúc 22, Tháng 11, 2025, 0:55

  lời giải có tâm