[ Solved ] [BT][Sắp xếp]

[hailoc12]

Tổ chức tham quan

Trong đợt tổ chức đi tham quan danh lam thắng cảnh của thành phố Hồ Chí Minh, Ban tổ chức hội thi Tin học trẻ tổ chức cho N đoàn (đánh từ số 1 đến N) mỗi đoàn đi thăm 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 Hoàng Đế di km (i=1,2,...., N). Hội thi có M xe taxi đánh số từ 1 đến M (M³N) để phục vụ việc đưa các đoàn đi thăm 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ụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.


Dữ liệu:File văn bản P2.INP:
- Dòng đầu tiên chứa hai 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ứ ba chứa các số nguyên dương v1, v2, ..., vM.
- Các số trên cùng một dòng được ghi khác nhau bởi dấu trắng.


Kết quả: Ghi ra file văn bản P2.OUT:
- Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi thăm quan (không tính lượt về);
- Dòng thứ i trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1, 2, ..., N).
Ví dụ:

INPUT
3 4
7 5 9
17 13 15 10
OUTPUT
256
2
3
4

[hailoc12]

Hướng dẫn thuật toán

Trước khi đọc những hướng dẫn dưới đây, hãy đảm bảo bạn đã dành thời gian suy nghĩ về bài toán, tìm hiểu kĩ lưỡng về INPUT, OUTPUT của nó. Tốt nhất nên cầm bút trong tay và làm thử vài ví dụ để tìm hiểu quy luật của bài toán. Chắc chắn bạn sẽ nhận ra bài toán không quá phức tạp như bạn tưởng.


Thuật toán:


- Cần phải chứng minh điều sau: Để tổng chi phí sử dụng xăng là nhỏ nhất thì xe tốn ít xăng hơn phải đựơc giao cho đoàn xa hơn, xe tốn nhiều xăng hơn sẽ dược giao cho đoàn gần hơn. Chú ý, bài này cũng như trong rất nhiều bài, phương án tối ưu có thể định nghĩa là phương án mà không tồn tại một cách thay đổi nào trển phương án đấy mà cho kết quả nhỏ hơn ( hoặc lớn hơn ) kết quả hiện tại của phương án.
- Từ nhận định trên ta có thuật toán đơn giản sau:


1. sắp xếp giảm các đoàn theo khoảng cách
2. sắp xếp tăng các xe theo lượng xăng tiêu thụ
3. sau đó gán xe thứ i cho đoàn thứ i. Ta được kết quả tối ưu.

Và điều quan trọng cuối cùng, để thực sự hiểu được bài toán, các bạn phải bắt tay vào VIẾT CHƯƠNG TRÌNH.


Chúc vui !

[rox_rook]

cho anh hỏi HaiLoc bài này hình như đề bài chưa đủ thì phải, nói đúng hơn là hơi gò bó quá?

Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.

Giả sử xe thứ j (V[j], j = 1,2,3...M ) chạy được j km và tốn V[j] lít xăng thì giả sử đoàn thứ i đi thăm cách khách sạn d[i] km thì nếu 1 xe chỉ phục vụ 1 đoàn thì không nhất thiết phải "đi đúng số km" mà chỉ cần đi đủ ( hoặc dư ) số km thôi à ?

[hailoc12]

Anh chú ý đề bài, xe thứ j có thể chạy số km bất kì và mỗi km sẽ tốn một lượng xăng là vj. Vì thế bài toán đơn thuần chỉ là sắp xếp. Nếu đưa thêm giới hạn xe thứ j chỉ có thể đi được dj km thì bài toán sẽ phức tạp hơn. Em cũng chưa thử nghĩ tới trường hợp này.

[rox_rook]

Dựa theo ý tưởng của em, anh có cách giải như sau :
-Sắp xếp lại xe tốn nhiều xăng hơn.
-Đoàn đi xa hơn.
Sau đó ghép vào, đây là toàn bộ code, em có cách nào hay hơn thì post cho anh tham khảo nhé ! Thân !

#include <iostream>#include <iomanip> const int maxx = 1000; int Gasoline[maxx];int Distance[maxx];int subG[maxx], indexG[maxx];int subD[maxx], indexD[maxx]; int N; /*the number of touring-group*/int M; /*the number of bus */   void swap ( int *r, int *c )        {        int temp = *r;        *r = *c;        *c = temp;}  bool ascending ( int a, int b )  { return b < a; }  bool descending ( int a, int b ) { return b > a; }   void bubble ( int array[], int size, bool (*compare)(int, int ) )        {        for ( int i = 2; i <= size; i++ )                for ( int j = 1; j <= size-1; j++ )                        if ( (*compare) (array[j], array[j+1]) )                        {                                swap ( &array[j], &array[j+1] );                        }        }   void InputData()     {                cout << "Enter the number of group : " ;        cin >> N;        cout << "Enter the number of bus : ";        cin >> M;         cout << "----------------" << endl;         for ( int i = 1; i <= M; i++ )        {                cout << "The bus : "<< i << " cost : ";                cin >> Gasoline[i];                subG[i] = Gasoline[i];        }        for ( int i = 1; i <= N; i++ )        {                cout << "The group : "<< i << " distance : ";                cin >> Distance[i];                subD[i] = Distance[i];        }        /*luu giu index*/        for ( int i = 1; i <= M; i++ )        {                indexD[i] = i;                indexG[i] = i;        }}       /*Sort data follow order the car cost more gas serve the longer distance*/  void SortData()        {                 cout << endl << "-------------------------" << endl;        bubble ( subG, M, ascending );        bubble ( subD, N, descending);        }   void Process()     {         int sum = 0;        for ( int i = 1; i <= N; i++ )        {                sum = sum + subD[i]*subG[i];        }              cout << "The total gasoline consumed : " << sum;        cout << endl;                        /*Search for former index*/        int index_Gas = 1;        for ( int i = 1; i <= M; i++ )        {                for ( int j = 1; j <= M; j++ )                {                        if ( subG[i] == Gasoline[j] )                        {                                indexG[index_Gas] = j;                                index_Gas++;                        }                }        }                int index_Dis = 1;        for ( int i = 1; i <= N; i++ )        {                for ( int j = 1; j <= N; j++ )                {                        if ( subD[i] == Distance[j] )                        {                                indexD[index_Dis] = j;                                index_Dis++;                        }                }        }        /******************************************/        }void OutPut()     {        for ( int i = 1; i <= N; i++ )        {                cout << "The bus [" << indexG[i] << "]";                cout << " serves the group [" << indexD[i] << "]";                cout << endl;        }}        void main()     {        InputData();    SortData();    Process();    OutPut();        cin.get();}