Đề bài: Có n người cần mua dày, người i cần mua đôi dày có kích thước hi (i=1..n). Trong hiệu dày có m đôi dày, đôi dày i có kích thước là si. Nếu người i mà mua đôi dày j thì độ chênh lệch sẽ là
. Bài toán đặt ra là cần mua dày thế nào để cho tổng chênh lệch của cả n người là nhỏ nhất. Tất nhiên một đôi dày thì chỉ có một người mua và một người cũng chỉ mua một đôi dày.
Giới hạn:2<=n<=m<=100.
INPUT: Vào từ file shoes.inp + Dòng đầu là hai số m, n cách nhau một dấu cách. + Dòng thứ hai là m số nguyên dương s1,... ,sm trong đó si là kích thước đôi dày i, hai số cách nhau một dấu cách. + Dòng thứ ba là n số nguyên dương h1,...,hn trong đó hi là kích thước đôi dày mà người i cần, hai số cách nhau một dấu cách. OUTPUT: ghi ra file shoes.out + Dòng dầu là số chênh lệch nhỏ nhất + Dòng thứ hai là n số, số thứ i là số hiệu đôi dày mà người i mua. Hai số sát nhau cách nhau bởi một dấu cách. Ví dụ


Trong bài viết "Đôi điều về đề thi chọn học sinh giỏi quốc gia bảng B năm 2002 -2003" số báo tháng 5 (năm 2003), tác giả Đinh Xuân Hải đã giới thiệu với chúng ta về giải thuật ghép cặp đối với bài toán số 4 (Bài: Mua giày). Trong số này, tôi muốn giới thiệu với các bạn một thuật toán khác rất thú vị để giải quyết bài toán này: Thuật toán quy hoạch động.
Đề bài các bạn có thể xem lại trong số báo tháng 5 (năm 2003), ở đây tôi xin không nhắc lại nữa.
Trước tiên, Chúng ta cùng xét bài toán phụ sau:
Bài toán: Cho 2 dãy đơn điệu tăng (a1,a2,...,an) và (b1,b2,b3,...,bn). Dãy (c): c1,c2,...,cn là một hoán vị của dãy (b). Chứng minh rằng: |a1 -b1|+|a2 -b2|+...+|an -bn | <= |a1 -c1|+| a2 -c2|+...+|an-cn| (*).
Giải: +) Nếu đồng thời xảy ra đẳng thức ci=bi với mọi i=1..n thì (*) hiển nhiên đúng. +) Ngược lại ta suy ra luôn tồn tại ít nhất 1 cặp số ci>cj mà i Bằng cách xét các trường hợp của 4 số ai,aj, ci,cj ta dễ dàng chứng minh được: |ai-ci|+|aj -cj|>|ai-cj|+|aj -ci|. Suy ra …|ai -cj|+...+|aj-ci|+ …+|an-cn|< …|ai-ci|+ … +|aj-cj|+ …+|an-cn|. Đổi chỗ hai phần tử ci,cj và tiếp tục làm như trên với dãy (c). ta suy ra: Tổng S=|a1-c1|+|a2-c2|+...+|an-cn| là nhỏ nhất khi dãy (c) đơn điệu hay (c) Ξ (b). Vậy (*) luôn đúng.
Từ bài toán trên, ta có nhận xét để giải bài toán số 4 như sau: Giả sử tìm được cách thuê dày có độ lệch nhỏ nhất: Học sinh i đi đôi dày p[i]. Với 2 học sinh u và v bất kỳ: Nếu h[u] Cách thứ nhất. -Sắp xếp 2 mảng h,s tăng dần. Như vậy, các bạn cần thêm mảng cs1[i] để lưu chỉ số của học sinh i và mảng cs2[i] lưu chỉ số đôi dày i sau khi sắp xếp. -Xây dựng mảng 2 chiều L[N,M] có ý nghĩa: L[i,j] là tổng độ lệch nhỏ nhất nhất khi chỉ xét mua giầy cho các học sinh từ i tới N với các đôi giầy từ j..M (điều kiện: M-j>N-i). -Để xây dựng mảng L(N,M) cần xây dựng hàm đệ quy QHĐ(i,j) tìm giá trị độ lệch nhỏ nhất khi xét các học sinh từ 1..N, đôi giầy từ j..M.
Cần dung thêm mảng luu[i,j] là chỉ số đôi giầy mà học sinh i mua khi xét các đôi giày từ j..M. (luu[i,j] thuộc [j,M-N+i]). Các bạn chú ý bước 2 chúng ta làm với