Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Phân tích Bài Toán về xêp hàng khi mua vé

  1. #1
    Ngày gia nhập
    03 2010
    Bài viết
    11

    Mặc định Phân tích Bài Toán về xêp hàng khi mua vé

    Có N người xếp hàng mua vé. Ta đánh số thứ tự từ 1 đến N cho những người mua vé. Thời gian phục vụ bán vé cho người thứ i (0<i<=N) là ti. Mỗi người cần mau một vé nhưng mua được tối đa 2 vé. Vì thế một số người có thể nhờ người đứng ngay trứoc mình mua hộ, Nếu người thứ i nhận mua vé cho người thứ i+1 thì thời gian mua vé là ri. Tìm phuơng án sao cho tổng thời gian mua vé của N người là thấp nhất
    Dữ liệu vào từ File T.inp
    - dòng 1 ghi số N (1<N<=200)
    - Dòng thứ 2 ghi N số nguyên duơng ti
    - dòng thứ 3 ghi n-1 số nguyen duơng 2i

    kết quả ghi ra file t.out
    - dong thứ nhất ghi tổng thời gian phục vụ bán ve
    - dong thứ 2 ghi lại danh sach người mua vé với vị trí nhờ mua là 0
    vd:
    t.inp
    5
    2 5 7 8 4
    3 9 10 10
    t.out
    17
    1 0 3 0 5
    Hết
    Các bạn phân tích các giải
    code : da tim ra được thời gian tốt nhất nhưng xuất lại vị trí thì bó dep
    #include <fstream.h>
    #include <conio.h>
    #include <iostream.h>
    #include <math.h>
    using namespace std;



    struct node
    {
    int GT,TG;
    node *r,*l;
    int vt;



    };
    void nhap(int *&a,int *&b,int &sl)
    {
    ifstream f ("d:\\hai\\t.inp");
    if(!f.is_open())
    {
    cout<<"loi" ;

    }
    else
    {

    f>> sl;
    a=new int [sl];
    b=new int [sl];
    for (int i=0; i< sl;i++)
    f>> a[i];
    for (int i=0; i< sl-1;i++)
    f>>b[i];
    b[sl-1]=a[sl-1];




    }
    f.close();





    }

    void nhapcay(node *&h,int *a,int *b,int sl, int vt,int gt,int loai)
    {

    int *h1=a, *h2=b;



    int vt1= vt+1;
    if( vt1 <=sl+1)
    {
    h->TG=1;
    h->GT = gt;
    h->vt = vt;

    if( loai !=0) vt++;
    vt1=vt+1;
    h->r=new node;

    nhapcay(h->r,a,b,sl,vt1,a[vt],0);

    h->l=new node;
    nhapcay(h->l,h1,h2,sl,vt1,b[vt],1);


    }

    }



    int tim(node *h)
    {

    if( (h-> TG)!=1) return 0;
    else
    {


    return h->GT +fmin(tim(h->r),tim(h->l));



    }





    }



    int main()
    {
    node *h=new node;

    int *tm,*md,sl,tong=0,vt =0;
    nhap(tm,md,sl);
    nhapcay(h,tm,md,sl,0,0,0);
    tong = tim(h);
    cout<<tong<<endl;


    getch();
    return 0;

    }

  2. #2
    Ngày gia nhập
    12 2010
    Bài viết
    129

    bài này dùng quy hoạch động
    Hỏi một câu thì chỉ dốt trong chốc lát.
    Nhưng nếu không hỏi thì bạn sẽ dốt suốt đời.

    ƯỚC MƠ VẪN CHỈ LÀ ƯỚC MƠ NẾU CHỈ BIẾT ƯỚC MƠ MÀ KHÔNG CÓ SỰ NỖ LỰC

  3. #3
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Trích dẫn Nguyên bản được gửi bởi linhcodervn Xem bài viết
    bài này dùng quy hoạch động
    Chuẩn đấy. Code demo tí:
    Code:
    enum {TỰ_MUA = 0, NHỜ_NGƯỜI_TRƯỚC = 1, MIN = 2};
    enum {MỘT_SỐ_CỰC_TO = 0xFFFFFF};
    int time[MAXN + 1][3] = { {0, 0, 0} };
    for (int i = 1; i <= N; ++i) {
       time[i][TỰ_MUA] = time[i - 1][MIN] + t[i];
       time[i][NHỜ_NGƯỜI_TRƯỚC] = (i > 1 ? time[i - 2][MIN] + r[i - 1] : MỘT_SỐ_CỰC_TO);
       time[i][MIN] = std::min(time[i][TỰ_MUA], time[i][NHỜ_NGƯỜI_TRƯỚC]);
    }
    kết quả là time[N][MIN]
    Lần ngược:
    Code:
    std::vector<int> trace;
    for (int i = N; i > 0; --i) {
      if (time[i][MIN] == time[i][NHỜ_NGƯỜI_TRƯỚC]) {
        trace.push_back(0); 
        trace.push_back(--i); 
      }
      else trace.push_back(i);
    }
    rồi in trace theo thứ tự ngược lại là xong (giả sử ofs là stream của file output):
    Code:
    ofs << time[N][MIN] << std::endl;
    std::ostream_iterator<int> ofs_iter(ofs, " ");  // Cái này yêu cầu #include <iterator>
    std::copy(trace.rbegin(), trace.rend(), ofs_iter);

  4. #4
    Ngày gia nhập
    03 2010
    Bài viết
    11

    cũng rắc rối nhĩ
    cảm ơn 2 bạn mình đã hiểu nhưng có một thắc mắc là nếu cách trên của mình có thể làm sao lấy ra được vị trí hay không
    và cho hỏi về đoạn code lần ngược<giải thích >: thật sự chưa hiểu nguyên tắc hoạt động của vector

Các đề tài tương tự

  1. Kỹ thuật C Ngăn xêp + hàng đợii
    Gửi bởi demonwalkerx trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 09-12-2012, 10:58 PM
  2. sắp xêp danh sách tăng dần theo giai thuật vun đống........
    Gửi bởi ngocnam_it trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 16-10-2008, 09:06 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn