# TKNP
*sau Tết*

## Mô hình chung

while (l <= r) {
    mid = (l+r) / 2
    check(mid);
}

Cái khó của mỗi bài nằm ở hàm `check`

### Tài liệu
- https://vnoi.info/wiki/algo/basic/binary-search.md
- https://codeforces.com/edu/courses, đăng ký "Pilot course" và vào phần practice của 5 step.

## Tìm trong mảng:
+ tìm vị trí $j$ lớn nhất,
+ $a[j] \le v$ (cho trước $v$)

(maxle, minge)

## Mua bài
$f(x)$ = số tiền phải trả để mua $x$ bộ bài. Vậy phải tìm
+ $x$ lớn nhất
+ $f(x) \le C$

Làm tương tự như tìm trong mảng, nhưng không có sẵn mảng đó mà mỗi lần hỏi là phải tính lại $f$.
Ví dụ: `if (a[mid] > val)` chuyển thành `if (f(mid) > val)` (tự viết $f$ theo đề)

## Bảng cửu chương

### Kiến thức chung
tìm số thứ $k$ trong một mảng A có kích thước rất lớn
--> tạo hàm `cnt(x)` là số lượng số trong mảng A mà $\le x$
Giá trị thứ $k$ sẽ là:
+ $x$ nhỏ nhất
+ mà `cnt(x)` $\ge k$

### Hướng giải

Đếm xem có bao nhiêu cặp $i,j (1\le i,j\le n)$ mà $i \times j \le x$
Vậy chỉ cần chạy for $i$, lấy được giá trị lớn nhất có thể của $j = min(\lfloor\frac{x}{i}\rfloor, n)$
Thứ tự cần tìm = (Số lượng+1) / 2

## Kích thước mảng con lớn nhất
Bài toán vận dụng khá hay. Có hai hướng:
- TKNP đáp án: giả sử kích thước lớn nhất $\ge x$. Cứ coi như kích thước bằng đúng $x$, thử tính xem tổng của mọi mảng con độ dài $\le x$ có đúng là $<k$ thật không? (tuy nhiên việc tính này không đơn giản lắm [set, 2 con trỏ, prefix-sum, ...])
- Suy nghĩ đơn giản: Tại mỗi vị trí $i$, tìm vị trí $j$ xa nhất mà tổng đoạn $[i,j] < k$. Vậy đáp án là $\min(j-i+1)$ của các $i$.