Pilots (MPILOT)
Đề bài
Pilots (MPILOT)
Charlie sở hữu vài cái máy bay bà già và cần tối ưu chi phí để kiếm lời.
Có $N$ phi công ($N$ chẵn) và cần có $N/2$ phi hành đoàn. Mỗi phi hành đoàn gồm 2 người – 1 lái chính, 1 trợ lí. Lái chính phải cao tuổi hơn trợ lí. Hợp đồng cho mỗi phi công có ghi mức lương nếu anh ta là lái chính hoặc là trợ lí. Với mỗi hợp đồng thì lương lái chính lớn hơn lương trợ lí.
Tìm cách ghép cặp sao cho tổng lương phải trả cho $N$ người là ít nhất.
Input:
- Dòng đầu là $N$ ($N$ chẵn), số phi công, $2 \le N \le 10\,000$.
- $N$ dòng tiếp theo, mỗi dòng là 2 số $X$, $Y$ là lương phi công thứ $i$ nếu làm lái chính hoặc trợ lí, $1 \le Y \lt X \le 100\,000$. Các phi công sắp tăng dần theo tuổi.
Output: Lương nhỏ nhất cần trả.
4
5000 3000
6000 2000
8000 1000
9000 6000190006
10000 7000
9000 3000
6000 4000
5000 1000
9000 3000
8000 600032000Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bài này mình áp dụng kiến thức về đệ quy (vét cạn), rồi quy hoạch động (cả top-down lẫn bottom-up, và rút gọn mảng 2 chiều về 1 chiều giống bài Perfect Sum Problem), cuối cùng là tham lam với hàng đợi ưu tiên.
Mình tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu: cho $N$ phi công ($N$ chẵn), cần ghép thành $N/2$ cặp. Mỗi cặp gồm 1 lái chính + 1 trợ lý (mình gọi trợ lý là lái phụ luôn nha), lái chính phải lớn tuổi hơn lái phụ. Phi công thứ $i$ làm lái chính thì nhận lương $X[i]$, làm lái phụ thì nhận $Y[i]$, và $X[i] \gt Y[i]$. Các phi công đã được sắp tăng dần theo tuổi, nên phi công số lớn hơn thì già hơn. Tìm cách ghép để tổng lương ít nhất.
Giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Mình viết cặp dưới dạng (lái chính, lái phụ) bằng số thứ tự phi công:
- Sample 1: $X = \{5000, 6000, 8000, 9000\}$, $Y = \{3000, 2000, 1000, 6000\}$. Ghép $(2, 1)$ và $(4, 3)$: tiền phải trả $= X[2] + Y[1] + X[4] + Y[3] = 6000 + 3000 + 9000 + 1000 = 19000$.
- Sample 2: $X = \{10000, 9000, 6000, 5000, 9000, 8000\}$, $Y = \{7000, 3000, 4000, 1000, 3000, 6000\}$. Ghép $(3, 1)$, $(4, 2)$, $(6, 5)$: tiền phải trả $= X[3] + Y[1] + X[4] + Y[2] + X[6] + Y[5] = 6000 + 7000 + 5000 + 3000 + 8000 + 3000 = 32000$.
Để ý phi công $1$ (trẻ nhất) bắt buộc làm lái phụ, còn phi công $N$ (già nhất) bắt buộc làm lái chính.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn bằng đệ quy
Cách làm đơn giản nhất là vét cạn: tạo ra mọi cách ghép cặp có thể, kiểm tra hợp lệ, tính tiền rồi lấy số tiền nhỏ nhất. Nghĩ thì rất đơn giản, nhưng bắt tay vào cài đặt "ghép cặp" thì sẽ rất phức tạp. Nên mình đi luôn vào một ý tưởng để vét cạn gọn hơn. Ta cần làm rõ và giả định vài thứ:
Làm rõ: các phi công được sắp tăng dần theo tuổi. Phi công $i$ khi ghép với các phi công $1 \ldots i-1$ thì làm lái chính, còn khi ghép với các phi công $i+1 \ldots n$ thì làm lái phụ. Nghe có vẻ hiển nhiên, nhưng chốc nữa ta sẽ làm hơi "ngược" nó một chút 😉.
Giả định: ta thuê $n$ phi công, trong đó $cnt$ người làm lái chính, những người còn lại làm lái phụ. Vì mỗi lái chính phải đi cùng một lái phụ nên số lái chính không được quá một nửa: $cnt \le n / 2$. Ta cho phép có những lái phụ đi một mình, không ghép với lái chính nào. Ví dụ thuê 6 phi công mà chỉ 1 lái chính: 5 người còn lại làm lái phụ, 1 lái phụ đi cùng lái chính, 4 lái phụ đi một mình.
Giả định như vậy có ích gì? Thuê $n$ phi công thì càng nhiều lái chính càng tốn tiền (lương lái phụ rẻ hơn mà). Rẻ nhất là tất cả làm lái phụ. Rồi ta tìm số tiền ít nhất khi có 1 lái chính, 2 lái chính, …, tăng dần tới $n/2$ lái chính thì đúng yêu cầu đề. Nên $0 \le cnt \le n/2$.
Ý rất quan trọng: những lái phụ đi một mình thì không bị ràng buộc "trẻ hơn lái chính" nữa. Nên khi xét $i$ người đầu tiên với $cnt$ lái chính, người thứ $i$ (già nhất trong $i$ người) cũng có thể làm lái phụ – đứng một mình tạm thời, để sau này ghép với một lái chính già hơn ($i+1$, $i+2$, …).
Điều kiện dừng:
- Số lái chính quá một nửa: $cntMainPilots \gt n / 2$ – trường hợp không hợp lệ. Hàm đang tìm số tiền ít nhất nên ta trả về một giá trị rất lớn để không ảnh hưởng kết quả. Tệ nhất thì lương lái chính $10^5$, lái phụ $10^5 - 1$, nên tổng tiền tối đa xấp xỉ $10^5 \cdot 10^4 = 10^9$. Vậy cần trả về giá trị $\gt 10^9$. Hàm kiểu
intthì mình trả về $2^{30}$ (1<<30, phép dịch bit trái; $2^{30} \approx 1.07 \cdot 10^9 \gt 10^9$). Không nên trả về giá trị tối đa củaint, vì cộng thêm gì vào là tràn số ngay. - Hết phi công: $n = 0$ thì không thuê ai, trả về $0$.
Xử lý chạy: đến đây chắc chắn $n \gt 0$ và $cntMainPilots \le n/2$. Có 2 trường hợp lớn:
- Không thuê lái chính nào ($cntMainPilots = 0$): cả $n$ người làm lái phụ. Số tiền = (tiền thuê $n - 1$ người đầu với $0$ lái chính) + (phi công $n$ làm lái phụ) =
Try(n - 1, cntMainPilots) + Y[n]. - Còn lại ($1 \le cntMainPilots \le n/2$), xét phi công thứ $n$ có 2 lựa chọn:
- Làm lái chính: trước đó chỉ cần $n - 1$ người với $cntMainPilots - 1$ lái chính. Vì số lái chính $\le$ một nửa nên trong $n - 1$ người trước kiểu gì cũng có lái phụ để nó ghép cặp. Tiền:
Try(n - 1, cntMainPilots - 1) + X[n]. - Làm lái phụ (đứng một mình, chờ ghép với lái chính già hơn trong tương lai): trước đó vẫn cần đủ $cntMainPilots$ lái chính trong $n - 1$ người. Tiền:
Try(n - 1, cntMainPilots) + Y[n].
mincủa 2 lựa chọn. - Làm lái chính: trước đó chỉ cần $n - 1$ người với $cntMainPilots - 1$ lái chính. Vì số lái chính $\le$ một nửa nên trong $n - 1$ người trước kiểu gì cũng có lái phụ để nó ghép cặp. Tiền:
Try(n, n / 2): thuê $n$ phi công với đúng $n/2$ lái chính.Liệu có sai khi cho phi công thứ $n$ (già nhất) làm lái phụ? Thử với sample 2, $n = 6$: Try(6, 3) = min(Try(5, 2) + X[6], Try(5, 3) + Y[6]). Mà Try(5, 3) không hợp lệ: thuê 5 người thì tối đa $5 / 2 = 2$ lái chính (3 lái chính cần 3 lái phụ, tổng 6 người mà ta chỉ có 5), nên nó trả về $2^{30}$. Vậy chắc chắn Try(6, 3) = Try(5, 2) + X[6] – phi công thứ 6 làm lái chính, ghép với lái phụ đang đứng một mình trong 5 người trước đó. Nó khá rối đúng không 😅, nếu thấy rối các bạn thử đổi tên "xét $n$ người đầu tiên" thành "xét $i$ người đầu tiên" xem, biết đâu dễ hình dung hơn.
Các bạn có thể tham khảo source code về ý tưởng trên ở dưới đây, có khi nó sẽ dễ hiểu hơn đó:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int nMax = (int)1e4 + 5;
int X[nMax], Y[nMax];
int Try(int n, int cntMainPilots) {
if(cntMainPilots > (n / 2)) {
return (1<<30);
}
if(n == 0) {
return 0;
}
if(cntMainPilots == 0) {
return Try(n - 1, cntMainPilots) + Y[n];
}
return min(Try(n - 1, cntMainPilots - 1) + X[n], Try(n - 1, cntMainPilots) + Y[n]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> X[i] >> Y[i];
}
cout << Try(n, n / 2);
return 0;
}import sys
sys.setrecursionlimit(100000)
INF = 1 << 30
def Try(n, cntMainPilots):
if cntMainPilots > n // 2:
return INF
if n == 0:
return 0
if cntMainPilots == 0:
return Try(n - 1, cntMainPilots) + Y[n]
return min(Try(n - 1, cntMainPilots - 1) + X[n], Try(n - 1, cntMainPilots) + Y[n])
data = sys.stdin.read().split()
n = int(data[0])
X = [0] * (n + 1)
Y = [0] * (n + 1)
for i in range(1, n + 1):
X[i] = int(data[2 * i - 1])
Y[i] = int(data[2 * i])
print(Try(n, n // 2))Giải thích 1 số chỗ trong code ở trên:
- 3 dòng đầu hàm main (
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);) giúp đẩy nhanh tốc độ nhập xuất nếu các bạn code C++. Bài này đầu vào có thể tới $2 \cdot 10^4$ số nên các bạn nên thêm vào nha. const int nMax = (int)1e4 + 5;là giá trị tối đa của $n$ ($10^4$), mình hay cộng thêm 5 cho chắc.return (1<<30);chính là return $2^{30}$ đó nha.
Cách 2Đệ quy có nhớ (QHĐ top-down)
Thực sự mà nói, nghĩ ra ý tưởng trên rồi cài đặt được thì rất khoai đúng không anh em 😅. Nhưng đã có ý tưởng rồi thì không khó để làm luôn quy hoạch động. Code trên lâu vì Try(n, cntMainPilots) đã tính rồi mà gặp lại vẫn phải tính lại. Ta lưu kết quả lại:
- Cả 2 tham số $n$ và $cntMainPilots$ đều thay đổi khi gọi đệ quy, nên tạo mảng 2 chiều $F$, với $F[n][cntMainPilots]$ lưu kết quả của
Try(n, cntMainPilots). - $n$ tối đa $10^4$, $cntMainPilots$ tối đa $10^4 / 2$, nên mảng là
f[nMax][nMax / 2], khai báo toàn cục để tránh tràn bộ nhớ stack. - Hàm không bao giờ trả về $-1$, nên lấp đầy $F$ bằng $-1$. Sau điều kiện dừng, nếu
f[n][cntMainPilots] != -1thì trả về luôn; ngược lại tính rồi lưu vào.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int nMax = (int)1e4 + 5;
int X[nMax], Y[nMax];
int f[nMax][nMax / 2];
int Try(int n, int cntMainPilots) {
if(cntMainPilots > (n / 2)) {
return (1<<30);
}
if(n == 0) {
return 0;
}
if(f[n][cntMainPilots] != -1) {
return f[n][cntMainPilots];
}
if(cntMainPilots == 0) {
return f[n][cntMainPilots] = Try(n - 1, cntMainPilots) + Y[n];
}
return f[n][cntMainPilots] = min(Try(n - 1, cntMainPilots - 1) + X[n], Try(n - 1, cntMainPilots) + Y[n]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
fill(&f[0][0], &f[n][(n / 2) + 1], -1);
for(int i = 1; i <= n; ++i) {
cin >> X[i] >> Y[i];
}
cout << Try(n, n / 2);
return 0;
}import sys
import threading
INF = 1 << 30
def main():
data = sys.stdin.read().split()
n = int(data[0])
X = [0] * (n + 1)
Y = [0] * (n + 1)
for i in range(1, n + 1):
X[i] = int(data[2 * i - 1])
Y[i] = int(data[2 * i])
f = [[-1] * (n // 2 + 1) for _ in range(n + 1)]
def Try(n, cntMainPilots):
if cntMainPilots > n // 2:
return INF
if n == 0:
return 0
if f[n][cntMainPilots] != -1:
return f[n][cntMainPilots]
if cntMainPilots == 0:
f[n][cntMainPilots] = Try(n - 1, cntMainPilots) + Y[n]
else:
f[n][cntMainPilots] = min(Try(n - 1, cntMainPilots - 1) + X[n],
Try(n - 1, cntMainPilots) + Y[n])
return f[n][cntMainPilots]
print(Try(n, n // 2))
sys.setrecursionlimit(1000000)
threading.stack_size(512 * 1024 * 1024)
t = threading.Thread(target=main)
t.start()
t.join()Giải thích: fill(&f[0][0], &f[n][(n / 2) + 1], -1); là lấp đầy mảng $F$ bằng $-1$ (từ ô $f[0][0]$ tới hết ô $f[n][n/2]$). Không biết hàm fill thì dùng vòng for cũng được, độ phức tạp như nhau.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n^2 / 2)$. Mảng $F$ rất to: $n = 10^4$ thì chứa $5 \cdot 10^7$ phần tử. Giới hạn bộ nhớ bài cho là 256 MB, code này chiếm tới khoảng 200 MB – rất suýt soát.
- Thời gian: $O(n^2 / 2)$. Trường hợp xấu nhất phải lấp đầy mảng $F$, cỡ $5 \cdot 10^7$ phép tính, vẫn dưới 1 giây nên AC được (mình đo khoảng 0.4 giây).
Đây chưa phải cách tốt nhất (lâu và tốn bộ nhớ), nhưng khi đi thi thì anh em cứ ưu tiên cách nào làm nhanh nhất và đúng nhất để AC nha.
Cách 3Quy hoạch động bottom-up – O(N²)
Đã có top-down thì cũng có bottom-up. Công thức truy hồi giống hệt phần top-down, chỉ cần thay $n = i$ (số phi công đã xét) và $cntMainPilots = j$ (số lái chính). Nhưng mình sẽ trình bày lại theo 4 bước, cho trường hợp các bạn nghĩ thẳng ra QHĐ mà không làm 2 cách trên:
Bước 1: Xác định bài toán con
Gọi $F[i][j]$ là số tiền ít nhất phải trả để thuê $i$ phi công đầu tiên, trong đó có $j$ phi công là lái chính, những người còn lại làm lái phụ, với $0 \le j \le i / 2$. Ta chấp nhận có nhiều lái phụ hơn lái chính ở các trường hợp $j \lt i/2$ hoặc ($j = i/2$ nhưng $i$ lẻ) – những trường hợp đó vẫn đúng là "số tiền ít nhất" (càng nhiều lái phụ càng đỡ tốn tiền 😁), và nhờ chúng ta xây dựng được các trường hợp với nhiều phi công và nhiều lái chính hơn.
Bước 2: Xác định trường hợp cơ sở
Những trường hợp số lái chính quá một nửa ($j \gt i/2$) là không hợp lệ. Ví dụ 6 phi công thì tối đa 3 lái chính; 7 phi công cũng chỉ tối đa $7 / 2 = 3$ lái chính (3 lái chính đi kèm 3 lái phụ, người dư làm lái phụ đứng một mình). Ta đang tìm min, nên các ô không hợp lệ gán bằng giá trị rất lớn mà chắc chắn không bao giờ phải trả nhiều đến thế: lớn hơn $10^9$. Mình chọn $2^{30}$ (lớn hơn $10^9$ và nhỏ hơn INT_MAX).
long long cho đỡ lo tràn? Làm thế là chết á 😱. Mảng $F$ có khoảng $n \cdot n/2 = 5 \cdot 10^7$ phần tử; long long mỗi phần tử 8 byte nên cần $4 \cdot 10^8$ byte $\approx 381$ MB – quá giới hạn 256 MB. Còn int thì chỉ một nửa, khoảng 190 MB. Không gán bằng INT_MAX ($2^{31} - 1$) vì cộng thêm $Y[i]$ vào là tràn. Với $2^{30}$ thì $2^{30} + 10^5$ vẫn còn trong phạm vi int.Khi không thuê ai ($i = 0$) thì số lái chính là $0$ và tiền là $0$: $F[0][0] = 0$. Tóm lại: f[0][0] = 0; và fill(&f[0][1], &f[n][(n / 2) + 1], 1<<30); (lấp đầy $2^{30}$ trừ ô $F[0][0]$).
Bước 3: Xác định đáp án của bài toán
Hiển nhiên là $F[n][n/2]$: số tiền ít nhất cho $n$ phi công với $n/2$ lái chính.
Bước 4: Xác định công thức truy hồi
- $j = 0$: phi công $i$ làm lái phụ: $F[i][0] = F[i-1][0] + Y[i]$.
- $1 \le j \le i/2$: phi công $i$ hoặc làm lái chính (nó già nhất trong $i$ người nên ghép được với bất kỳ lái phụ nào): $F[i-1][j-1] + X[i]$; hoặc làm lái phụ (đứng một mình, chờ ghép với lái chính già hơn trong tương lai): $F[i-1][j] + Y[i]$.
$F[i][j] = \min\big(F[i-1][j-1] + X[i],\ F[i-1][j] + Y[i]\big)$ với $1 \le j \le i/2$
Trên bảng: ô $(i, j)$ = min(ô chéo trên-trái + $X[i]$, ô ngay trên + $Y[i]$).
Công thức có đúng không, khi phi công $1$ bắt buộc là lái phụ và phi công $n$ bắt buộc là lái chính? Các bạn nên lấy nháp vẽ bảng $F$ ra là thấy ngay:
- Phi công 1: $F[1][0] = F[0][0] + Y[1]$ (làm lái phụ); còn $F[1][1]$ không hợp lệ vì $1 / 2 = 0$, giữ $2^{30}$.
- Với $n = 6$, tại $j \lt n/2$ phi công thứ $n$ vẫn có thể làm lái phụ đứng một mình. Nhưng tại $j = n/2$: $F[6][3] = \min(F[5][2] + X[6],\ F[5][3] + Y[6])$, mà $F[5][3]$ không hợp lệ, nên chắc chắn $F[6][3] = F[5][2] + X[6]$ – phi công thứ $n$ làm lái chính. Vì $n$ chẵn và cần $n/2$ lái chính thì với $n - 1$ người không thể có $n/2$ lái chính được.
Minh hoạ: lấp bảng F[i][j]
Các bạn nhập lương lái chính $X$ và lái phụ $Y$ rồi bấm Tiếp. Ô vàng là ô đang tính, ô tím viền là 2 ô nó lấy từ đó; ∞ là $2^{30}$ (không hợp lệ):
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int nMax = (int)1e4 + 5;
int X[nMax], Y[nMax];
int f[nMax][nMax / 2];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
f[0][0] = 0;
fill(&f[0][1], &f[n][(n / 2) + 1], 1<<30);
for(int i = 1; i <= n; ++i) {
cin >> X[i] >> Y[i];
}
for(int i = 1; i <= n; ++i) {
f[i][0] = f[i - 1][0] + Y[i];
for(int j = 1; j <= i / 2; ++j) {
f[i][j] = min(f[i - 1][j - 1] + X[i], f[i - 1][j] + Y[i]);
}
}
cout << f[n][n / 2];
return 0;
}import sys
INF = 1 << 30
data = sys.stdin.read().split()
n = int(data[0])
X = [0] * (n + 1)
Y = [0] * (n + 1)
for i in range(1, n + 1):
X[i] = int(data[2 * i - 1])
Y[i] = int(data[2 * i])
f = [[INF] * (n // 2 + 1) for _ in range(n + 1)]
f[0][0] = 0
for i in range(1, n + 1):
f[i][0] = f[i - 1][0] + Y[i]
for j in range(1, i // 2 + 1):
f[i][j] = min(f[i - 1][j - 1] + X[i], f[i - 1][j] + Y[i])
print(f[n][n // 2])Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n^2 / 2)$ – chủ yếu do mảng $f$, mảng $X$, $Y$ không đáng kể. Mình đo thực tế khoảng 194 MB (đúng như tính toán ~190 MB, phần lệch là do mảng $X$, $Y$).
- Thời gian: $O(n^2)$, vì bước lấp đầy mảng $F$ bằng $2^{30}$ tệ nhất phải lấp đầy toàn mảng; còn 2 vòng
forlồng nhau chỉ tốn $O(n^2 / 2)$.
So với top-down thì code này chạy nhanh hơn rất nhiều và ăn ít bộ nhớ hơn (không tốn cho đệ quy). Nhưng vẫn phải dùng mảng 2 chiều rất lớn.
Cách 4Rút gọn về mảng 1 chiều – bộ nhớ O(N)
Giống bài Perfect Sum Problem, ta cải tiến mảng $F$ từ 2 chiều về 1 chiều, tiết kiệm bộ nhớ hơn rất nhiều. Bỏ chiều $[i]$ đi: khai báo int F[nMax / 2];. Lúc này $F[j]$ là số tiền ít nhất để có $j$ lái chính khi đã thuê $i$ phi công đầu tiên (vòng for(i) vẫn chạy ở ngoài, chỉ là bỏ $[i]$ khỏi $F$).
- Cơ sở: $F[0] = 0$, các phần tử khác $= 2^{30}$. Đến cuối, khi $i = n$, thì $F[n/2]$ là đáp án.
- Thứ tự tính: vòng
for(i)giữ nguyên; bên trong đảo ngược lại: chạy vòngfor(j)ngược từ $i/2$ về $1$ trước, xong mới cập nhật $F[0]$.
for(int j = i / 2; j >= 1; --j) F[j] = min(F[j - 1] + X[i], F[j] + Y[i]);F[0] += Y[i];Vì $j$ chạy ngược nên lúc tính $F[j]$ thì $F[j-1]$ chưa được xét ở vòng $i$ này, bản chất vẫn là $F[i-1][j-1]$. Còn $F[j]$ đang xét nhưng chưa cập nhật, bản chất là $F[i-1][j]$. $F[0]$ cập nhật cuối cùng nên lúc tính $F[1]$ nó vẫn là $F[i-1][0]$. Vậy công thức hoàn toàn đúng.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int nMax = (int)1e4 + 5;
int X[nMax], Y[nMax], f[nMax / 2];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
f[0] = 0;
fill(&f[1], &f[(n / 2) + 1], (1<<30));
for(int i = 1; i <= n; ++i) {
cin >> X[i] >> Y[i];
}
for(int i = 1; i <= n; ++i) {
for(int j = i / 2; j >= 1; --j) {
f[j] = min(f[j - 1] + X[i], f[j] + Y[i]);
}
f[0] += Y[i];
}
cout << f[n / 2];
return 0;
}import sys
INF = 1 << 30
data = sys.stdin.read().split()
n = int(data[0])
X = [0] * (n + 1)
Y = [0] * (n + 1)
for i in range(1, n + 1):
X[i] = int(data[2 * i - 1])
Y[i] = int(data[2 * i])
f = [INF] * (n // 2 + 1)
f[0] = 0
for i in range(1, n + 1):
x, y = X[i], Y[i]
for j in range(i // 2, 0, -1):
f[j] = min(f[j - 1] + x, f[j] + y)
f[0] += y
print(f[n // 2])Đánh giá độ phức tạp: thời gian vẫn như cách trên, nhưng không gian chỉ còn $O(n)$ (đúng ra là $O(2n + n/2)$ cho mảng $X$, $Y$, $F$, theo quy tắc Big-O là $O(n)$). Nhờ rút gọn bộ nhớ, và truy cập mảng 1 chiều nhanh hơn mảng 2 chiều, nên code chạy nhanh hơn và ăn ít bộ nhớ hơn rất nhiều lần (mình đo $n = 10^4$: khoảng 0.03 giây, 11 MB). Tuy vậy nhìn bảng xếp hạng thì đây vẫn chưa phải cách nhanh nhất.
Cách 5Tham lam với hàng đợi ưu tiên – O(N log N)
Cách nhanh nhất là dùng kỹ thuật tham lam (Greedy). Nói nhanh cho bạn nào chưa biết: tham lam là mỗi khi đứng trước nhiều lựa chọn thì chọn cách tốt nhất ở hiện tại rồi đi theo nó; lại gặp nhiều lựa chọn thì lại chọn cái tốt nhất – cứ tốt nhất mà triển, nên mới gọi là tham lam. Nó không có công thức từng bước cụ thể như các thuật toán khác, miễn tư tưởng là luôn chọn theo hướng tốt nhất.
Điều gì khiến ta thuê rẻ hơn? So sánh: thuê $i$ phi công tất cả làm lái chính, với thuê $i$ phi công tất cả làm lái chính trừ phi công $i$ làm lái phụ. Chênh lệch chính là $X[i] - Y[i]$ – đổi phi công $i$ từ lái chính sang lái phụ sẽ giảm đúng lượng tiền đó. Ví dụ sample 1: thuê 2 phi công đầu đều làm lái chính tốn $11000$; bắt phi công 2 làm lái phụ thì còn $11000 - (6000 - 2000) = 7000$; bắt phi công 1 làm lái phụ thì còn $11000 - (5000 - 3000) = 9000$.
Ý tưởng: xét lần lượt từng phi công (từ trẻ đến già):
- Cứ cho phi công $i$ làm lái chính trước: cộng $X[i]$ vào kết quả, và đẩy độ chênh lệch $X[i] - Y[i]$ vào hàng đợi ưu tiên.
- Nếu $i$ lẻ: trong $i$ người đầu tiên phải có ít nhất $(i + 1)/2$ lái phụ (để các lái chính sau này có người ghép). Ta cần chọn thêm 1 người làm lái phụ – tham lam chọn người có chênh lệch lớn nhất trong số các lái chính hiện tại và phi công $i$ (chênh lệch càng nhiều thì giảm tiền càng nhiều). Trừ chênh lệch đó khỏi kết quả và bỏ nó ra khỏi hàng đợi.
- Nếu $i$ chẵn: cứ để nó làm lái chính.
Tại sao được chọn một lái chính lúc trước làm lái phụ? Được chứ: chọn lái chính trước đó làm lái phụ thì cử phi công mới vào thế chỗ làm lái chính, phi công mới đang già nhất mà. Còn nếu chính phi công $i$ có chênh lệch lớn nhất thì nó làm lái phụ.
Để lấy phần tử lớn nhất nhanh, ta dùng priority_queue (hàng đợi ưu tiên) của C++: ở chế độ mặc định phần tử đầu (top()) luôn là phần tử lớn nhất; thêm (push) và xoá (pop) chỉ mất $O(\log N)$, xem phần tử đầu mất $O(1)$. Rất hợp để áp dụng vào bài này.
Minh hoạ: tham lam từng phi công
Các bạn bấm Tiếp: khung xanh dương là lái chính, xanh lá là lái phụ; dòng dưới là hàng đợi ưu tiên (ô vàng là top()). Bước cuối mình ghép cặp lại để các bạn thấy cách chọn của tham lam luôn ghép được hợp lệ:
Cách trên khá khó hình dung, nhưng mình nghĩ các bạn nhìn vào code thì sẽ dễ thấy ý tưởng hơn đó. Source code để các bạn tham khảo:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
priority_queue<int> pq;
int res = 0;
for(int i = 1; i <= n; ++i) {
int x, y;
cin >> x >> y;
res += x;
pq.push(x - y);
if(i % 2) {
res -= pq.top();
pq.pop();
}
}
cout << res;
return 0;
}import sys
import heapq
data = sys.stdin.read().split()
n = int(data[0])
pq = [] # heapq là min-heap nên ta lưu số đối (-(x - y)) để lấy được max
res = 0
for i in range(1, n + 1):
x = int(data[2 * i - 1])
y = int(data[2 * i])
res += x
heapq.heappush(pq, -(x - y))
if i % 2:
res -= -heapq.heappop(pq)
print(res)Giải thích 1 số chỗ trong code ở trên:
priority_queue<int> pq;lưu độ chênh lệch giữa làm lái chính và làm lái phụ của những người đang làm lái chính (và phi công lẻ đang xét – người đang đứng trước lựa chọn bị chọn làm lái phụ hoặc làm lái chính thay cho người khác).res += x;cứ cho phi công $i$ làm lái chính đã, rồi mới tính chuyện chênh lệch.if(i % 2) { res -= pq.top(); pq.pop(); }: $i$ lẻ thì chọn ra người lái phụ tiềm năng nhất (chênh lệch lớn nhất) trong những người đang làm lái chính cộng phi công $i$. Nếu người đó chính là phi công $i$ thì đơn giản là phi công $i$ nhận lương lái phụ; nếu không thì phi công $i$ thế chỗ làm lái chính cho người được chọn. Sau đó nhớ xoá chênh lệch đó khỏipq. Còn $i$ chẵn thì chỉ đẩy chênh lệch vàopq, để nhỡ tương lai sẽ chọn nó làm lái phụ.- Bản Python dùng
heapq– là min-heap – nên mình lưu số đối-(x - y)để lấy được phần tử lớn nhất.
Đánh giá độ phức tạp của cách làm này:
- Không gian: bỏ được cả mảng $X$, $Y$ lẫn mảng $f$, chỉ dùng
priority_queuechứa tối đa khoảng $n/2$ phần tử: $O(n / 2)$. - Thời gian: một vòng
for(i), mỗi lần thêm/xoá trên hàng đợi kích thước $n/2$ mất $O(\log(n/2))$, nên tổng $O(n \cdot \log(n / 2))$.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét