Giúp thuật toán cho bài tập tham quan
Đề bài : Trong đợt tổ chức đi tham quan các danh lam thắng cảnh ở Ninh Thuận, Ban tổ
chức hội khỏe phù đổng tổ chức cho n đoàn (đánh số từ 1 đến n) mỗi đoàn đi tham quan một địa điểm khác nhau. Đoàn thứ i đi thăm địa điểm cách khách sạn Con Gà Vàng di km (i=1,2,3…n). Hội thao có m xe đánh số từ 1 đến m (m>=n) để phục vụ việc đưa các đoàn đi tham quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích/km.
Yêu cầu: Hãy chọn n xe phục vụ các đoàn đi tham quan, mỗi xe chỉ phục vụ
một đoàn sao cho tổng chi phí xăng dầu là ít nhất.
Dữ liệu vào: file văn bản thamquan.inp.
- Dòng đầu tiên chứa 2 số nguyên dương n,m (n<=m<=200);
- Dòng thứ hai chứa các số nguyên dương d1,d2,…dn;
- Dòng thứ 3 chứa các số nguyên dương v1,v2,…vn.
- Các số trên cùng một dòng được ghi cách nhau một khoảng trống.
Kết quả: Ghi ra file văn bản thamquan.out - Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng đưa các đoàn đi thăm quan (không tín lượt về);
- Dòng thứ i trong số n dòng tiếp theo ghi chỉ số xe phục vụ các đoàn
(i=1,2,3,…n)
Ví dụ:
3 4
7 5 9
17 13 15 10
Output :
256
2
3
4
Ý tưởng của em : Vì để tiết kiệm chi phí, thì em sẽ cho xe nào tốn ít xăng đi quãng đường dài hơn và xe nào tốn nhiều xăng sẽ đi quãng đường ít hơn, bằng cách :
+ Sort lại 2 mảng theo chiều tăng dần
+ Cho 2 biến đếm, 1 biến chạy tới (ở mảng b- số xăng tiêu thụ), 1 biến chạy lui (ở mảng a- số km), đồng thời cộng vào kết quả
Em đã xuất ra được số xăng tiêu thụ (256), nhưng không biết làm sao để xuất số xe ra, em nghĩ là dùng mảng lưu vị trí, nhưng khi sort lại thì vị trí xuất ra sẽ không được như output của đề bài. Các anh/chị giúp em được không ạ ?
Dùng
pair<int, int>
hoặcstruct { int value; int index; }
để lưu giá trị và vị trí của mỗi phần tử trong mảng xe ban đầu. Khi sort mảng xe thì ta sort theo value.Xin lỗi, em dùng Pascal nên không biết cái này, có cái nào tương tự mà dùng được trong pascal không ạ ?
Dùng record (kết hợp quicksort).
Góp ý: “thăm quan” là sai chính tả, “tham quan” mới đúng chính tả. Sửa title đi bạn.
Thế mà ban đầu đề tag c c++ như thật
Em mới lên daynhauhoc nên không biết ạ, cảm ơn anh