# Lời giải bài ACM

## Tác giả: Lê Nguyễn Hữu An, T2124

## 1. Tóm tắt đề

Cho $2n$ ($1 \leq n \leq 4.10^5$) bài toán, để giải bài toán thứ $i$ cần $a_{i}$ giây nếu giao cho Tí làm, hoặc cần $b_{i}$ giây nếu giao cho Tèo làm.

Hãy tìm cách phân công các bài toán cho Tí và Tèo, mỗi người làm đúng $n$ bài sao cho tổng thời gian giải cả $2n$ bài là ít nhất.

In ra tổng thời gian ít nhất tìm được.

## 2. Lời giải

Gọi $p_{1}, p_{2}...p_{n}$ là số hiệu các bài toán mà Tí giải, $q_{1}, q_{2}...q_{n}$ là số hiệu các bài toán mà Tèo giải (Điều kiện: $\forall 1 \leq i, j \leq n: 1\leq p_{i}, q_{j} \leq2n$ và $p_{i}\neq q_{j}$).

Khi đó tổng thời gian để giải 2n bài là:
$a_{p_{1}}+a_{p_{2}}+...+a_{p_{n}}+b_{q_{1}}+b_{q_{2}}+...+b_{q_{n}} = \sum_{i=1}^{n}a_{p_{i}} + \sum_{i=1}^{n}b_{q_{i}}$

**Nhận xét:** Ta luôn có $2a_{i} = a_{i} + b_{i} + (a_{i} - b_{i})$ và $2b_{i} = a_{i} + b_{i} - (a_{i} - b_{i}) \hspace{8pt}\forall 1 \leq i \leq n$

Do đó tổng (1) bằng với:
$^1/_2 \sum_{i=1}^{n}\left[a_{p_{i}} + b_{p_{i}} + (a_{p_{i}} - b_{p_{i}})\right]+ \frac{1}{2}\sum_{i=1}^{n}\left[a_{q_{i}} + b_{q_{i}} - (a_{q_{i}} - b_{q_{i}})\right]$

$= \ ^1/_2\left[\sum_{i=1}^{2n} (a_{i} + b_{i}) + \sum_{i=1}^{n}(a_{p_{i}} - b_{p_{i}}) - \sum_{i=1}^{n}(a_{q_{i}} - b_{q_{i}})\right]$

Dễ thấy để đạt được giá trị nhỏ nhất, ta cần phải tối thiểu hóa biểu thức:
\begin{equation}
\sum_{i=1}^{n}(a_{p_{i}} - b_{p_{i})} - \sum_{i=1}^{n}(a_{q_{i}} - b_{q_{i}})
\end{equation}

Có thể chọn p gồm n bài toán sao cho $a_{i}-b_{i}$ là nhỏ nhất, q gồm n bài toán sao cho $a_{i}-b_{i}$ là lớn nhất. Khi đó biểu thức (2) là nhỏ nhất.

Vậy, với mảng $dif: dif_{i}=a_{i}-b_{i}$ đã được sort theo thứ tự không giảm, tổng nhỏ nhất cần tìm là:
$^1/_2\left[\sum_{i=1}^{2n} (a_{i} + b_{i})+\sum_{i=1}^{n} dif_{i}-\sum_{i=n+1}^{2n}dif_{i}\right]$

**Độ phức tạp:** Ta cần sắp xếp một lần sort, do đó độ phức tạp có thể là $O(nlogn)$ $nếu \ dùng \ chia \ nhị \ phân$ hoặc $O(n + max{a})$ $nếu \ dùng \ counting \ sort$.
### Code mẫu: [Link](https://ideone.com/5YpN4T)