Quy hoạch độngTham lam
Mô tả
Tại khu bếp cơ đông chức Fanxi, mỗi buổi sáng tô chức rửa bát theo hai mâm chuẩn: mâm A và mâm B. Mỗi chiếc bát được dán một nhãn số nguyên để phân biệt loại. Vì nhu cầu thực tế thay đổi, quản lý bếp cần biến đổi mâm A thành mâm B bằng ba thao tác sau, mỗi thao tác tốn đúng 1 phút:
- Thêm một chiếc bát với nhãn bất kỳ vào một vị trí tuỳ chọn trong mâm.
- Bớt một chiếc bát ở vị trí bất kỳ.
- Đổi nhãn của một chiếc bát ở vị trí bất kỳ sang giá trị khác.
Bạn hãy viết hàm tìm số phút ít nhất để biến mâm A thành mâm B.
Đầu vào
Hàm nhận hai tham số:
a: mảng số nguyên — mâm bát ban đầu.b: mảng số nguyên — mâm bát mục tiêu.
Đầu ra
Trả về một số nguyên không âm là số phút (thao tác) tối thiểu cần thiết.
Ràng buộc
- Số phần tử mỗi mâm:
0 ≤ độ dài ≤ 1000. - Giá trị mỗi nhãn:
|nhãn| ≤ 10^9.
Ví dụ
Ví dụ 1:
- Đầu vào:
a = [2, 5, 7],b = [2, 5, 9]. - Đầu ra:
1. - Giải thích: Hai bát đầu đã khớp, chỉ cần đổi nhãn bát thứ ba từ
7sang9, tốn 1 phút.
Ví dụ 2:
- Đầu vào:
a = [1, 3, 5],b = [1, 2, 3, 4, 5]. - Đầu ra:
2. - Giải thích: Giữ nguyên bát
1và3. Thêm bát nhãn2vào vị trí thứ hai, thêm bát nhãn4vào vị trí thứ tư, tổng cộng 2 phút.
Ví dụ 3:
- Đầu vào:
a = [10, 20, 30],b = []. - Đầu ra:
3. - Giải thích: Cần bớt toàn bộ 3 chiếc bát để có mâm rỗng như mục tiêu.