Dãy Con Liên Tiếp Có Trung Vị Lớn Nhất

Algorithms Arrays Buổi 14 — Two Pointers & Sliding Window two-pointers
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions

Cho một mảng gồm n số nguyên phân biệt và hai số nguyên k, x. Tìm đoạn con liên tiếp có đúng k phần tử sao cho trung vị (phần tử thứ ⌈k/2⌉ khi sắp xếp tăng dần) là lớn nhất có thể.\ \ Để giải hiệu quả, hãy chuyển mỗi phần tử thành +1 nếu ≥ x, -1 nếu < x, rồi dùng two pointers tìm đoạn con có k phần tử mà tổng lớn nhất.\ \ Input:\

  • Dòng 1: Ba số nguyên n, k, x (1 ≤ k ≤ n ≤ 2·10^5, 1 ≤ x ≤ 10^9).\
  • Dòng 2: n số nguyên phân biệt a[i] (1 ≤ a[i] ≤ 10^9).\ \ Output:\
  • In ra tổng lớn nhất khi chuyển đổi (đánh giá mức độ trung vị ≥ x). Nếu tổng ≥ 1 thì trung vị ≥ x.\
  • Dòng 2: In ra chỉ số bắt đầu (1-indexed) của đoạn con tối ưu.
Ví dụ
Input Output
5 3 3
1 2 3 4 5
3
3
Draft saved