Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: Thuật toán bài toán tìm số đoạn nguyên lớn nhất

  1. #1
    Ngày gia nhập
    05 2010
    Nơi ở
    Nha Trang, Khánh Hòa
    Bài viết
    103

    Thumbs down Thuật toán bài toán tìm số đoạn nguyên lớn nhất

    Đề bài đc lấy từ vn.spoj.pl:

    Mirko có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì. Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa được lấy trước nó. Mirko tiếp tục cho đến khi không tìm được đoạn thoả mãn nữa. Yêu cầu


    Tìm số đoạn lớn nhất có thể lấy ra. Dữ liệu


    Dòng đầu tiên chứa số nguyên N, là số đoạn nguyên trong tập hợp.
    Dòng thứ i trong số N dòng sau, chứa 2 số nguyên A,B biểu thị cho đoạn i. Kết quả


    Một số duy nhất là kết quả của bài toán. Giới hạn


    1 <= N <= 100000
    1 <= A < B <= 1000000 Ví dụ

    Dữ liệu
    3
    1 6
    2 5
    3 4
    Kết quả
    3

    Dữ liệu
    6
    1 4
    1 5
    1 6
    1 7
    2 5
    3 5
    Kết quả
    5

    --------------------------------
    Ý tưởng của mình đối vs bài toán này là ban đầu ta quicksort sắp xếp toàn bộ các đoạn theo số A tăng dần, với ~ đoạn số A bằng nhau thì sắp
    xếp theo số B giảm dần, khi đó với số i bất kỳ, ta có đoạn thứ i hoặc chứa đoạn i+1 hoặc 2 đoạn giao nhau, không có trường hợp đoạn i+1
    chứa đoạn i.
    => gọi d[i] là số đoạn con nhiều nhất có thể lấy ra sau khi lấy d[i] (tính cả đoạn i) thì
    d[i]=d[j]+1 với j>i thỏa đầu B của j<=đầu B của i và d[j] lớn nhất.
    Vấn đề ở đây là làm cách nào để tìm ra số j nhanh nhất có thể, thay vì phải duyệt ngược trở lại từ i hoặc B(i)? Mong đc các bạn giúp đỡ ^^
    Ngày mai ra sao cũng chẳng biết nữa
    Mà có ra sao thì cũng chả sao

  2. #2
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Dùng BIT(Binary Index Tree) để giảm độ phức tạp cho mỗi truy vấn.

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  3. #3
    Ngày gia nhập
    05 2010
    Nơi ở
    Nha Trang, Khánh Hòa
    Bài viết
    103

    anh có thể giải thích kỹ hơn dùm em 1 chút đc ko ạ?
    Ngày mai ra sao cũng chẳng biết nữa
    Mà có ra sao thì cũng chả sao

  4. #4
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Tư tưởng n^2 của em đúng rồi, bây giờ chỉ cần giảm độ phức tạp trong việc tìm j từ O(n) xuống O(logn) thôi. Một cách dễ cài đặt nhất là dùng BIT.

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  5. #5
    Ngày gia nhập
    05 2010
    Nơi ở
    Nha Trang, Khánh Hòa
    Bài viết
    103

    Anh coi dùm em cái bài làm đc hok, sao em nộp lên spoj toàn ra 0k vs 0đ =.=' kiểm tra với test ví dụ thấy đúng mà :-s
    C++ Code:
    1. #include <fstream>
    2. using namespace std;
    3.  
    4. const long maxn=100000;
    5. const long maxm=1000001;
    6.  
    7. long *s,*t;
    8. long d[maxm];
    9. long n,m;
    10.  
    11. void input()
    12. {
    13.     ifstream f("");
    14.     f>>n;
    15.     s=new long[n];
    16.     t=new long[n];long i;
    17.     m=0;
    18.     for (i=0;i<n;i++)
    19.     {
    20.         f>>s[i]>>t[i];
    21.         m=(t[i]>m)?t[i]:m;
    22.     }
    23.     f.close();
    24. }
    25. void swap(long i,long j)
    26. {
    27.     long k=s[i];s[i]=s[j];s[j]=k;
    28.     k=t[i];t[i]=t[j];t[j]=k;
    29. }
    30. void quicksort(long d,long c)
    31. {
    32.     long l,r,m;
    33.     l=d;
    34.     r=c;
    35.     m=(d+c)/2;
    36.     if (d>=c) return;
    37.     do
    38.     {
    39.         while (s[l]<s[m]) l++;
    40.         while (s[r]>s[m]) r--;
    41.         if (l<=r)
    42.         {
    43.             if ((s[l]<s[r])||((s[l]==s[r])&(t[l]<t[r]))) swap(l,r);
    44.             l++;r--;
    45.         }
    46.     }
    47.     while (l<r);
    48.     if (d<r) quicksort(d,r);
    49.     if (l<c) quicksort(l,c);
    50. }
    51. //-----------Binary Index Tree------------
    52. void init_algo()
    53. {
    54.     long i;
    55.     for (i=0;i<n;i++) d[i]=0;
    56. }
    57. long getrs(long node)
    58. {
    59.     long i=node,max=0;
    60.     while (i>0)
    61.     {
    62.         max=(d[i]>max)?d[i]:max;
    63.         i-=(i&(-i));
    64.     }
    65.     return max;
    66. }
    67. void setvalue(long node,long delta)
    68. {
    69.     long i=node;
    70.     while (i<=m)
    71.     {
    72.         d[i]+=delta;
    73.         i+=(i&(-i));
    74.     }
    75. }
    76. void process()
    77. {
    78.     long i,max;
    79.     for (i=n-1;i>=0;i--)
    80.     {
    81.         max=getrs(t[i]);
    82.         setvalue(t[i],(max+1-d[t[i]]));
    83.     }
    84. }
    85. //----------------------------------------
    86. void output()
    87. {
    88.     ofstream f("");
    89.     f<<getrs(m);
    90.     f.close();
    91. }
    92.  
    93. int main()
    94. {
    95.     input();
    96.     quicksort(0,n-1);
    97.     init_algo();
    98.     process();
    99.     output();
    100.     return 0;  
    101. }
    Ngày mai ra sao cũng chẳng biết nữa
    Mà có ra sao thì cũng chả sao

  6. #6
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Mặc định Thuật toán bài toán tìm số đoạn nguyên lớn nhất

    Anh sort theo x giảm dần, với mỗi x bằng nhau thì sort theo y tăng dần.
    Code sẽ delete sau 24h
    C++ Code:
    1. delete
    Đã được chỉnh sửa lần cuối bởi hunterphu : 01-09-2011 lúc 08:50 PM.

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  7. #7
    Ngày gia nhập
    05 2010
    Nơi ở
    Nha Trang, Khánh Hòa
    Bài viết
    103

    code của a e up lên spoj thỳ kiu lỗi )
    Mà cái nhập xuất trên spoj là nhập xuất trên thiết bị chuẩn chứ ko phải trên file hả a?
    Ngày mai ra sao cũng chẳng biết nữa
    Mà có ra sao thì cũng chả sao

  8. #8
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Code AC rồi anh mới khoe chứ, em dùng trình biên dịch 4.0.0.8 đi

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  9. #9
    Ngày gia nhập
    05 2010
    Nơi ở
    Nha Trang, Khánh Hòa
    Bài viết
    103

    ax c++ 4.3.2 vs 4.0.0.8 có khác j nhau ko ạ? =='
    Mà bài của e sao ko AC đc??? E thử mấy test nhỏ nhỏ khác thấy đúng hết mà :(
    Ngày mai ra sao cũng chẳng biết nữa
    Mà có ra sao thì cũng chả sao

  10. #10
    Ngày gia nhập
    05 2010
    Nơi ở
    Nha Trang, Khánh Hòa
    Bài viết
    103

    bài e mới sửa đây :-s vẫn k AC đc
    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3.  
    4. const long maxn=100000;
    5. const long maxm=1000001;
    6.  
    7. long *s,*t;
    8. long d[maxm];
    9. long n,m;
    10.  
    11. void input()
    12. {
    13.     cin>>n;
    14.     s=new long[n];
    15.     t=new long[n];long i;
    16.     m=0;
    17.     for (i=0;i<n;i++)
    18.     {
    19.         cin>>s[i]>>t[i];
    20.         m=(t[i]>m)?t[i]:m;
    21.     }
    22. }
    23. void swap(long i,long j)
    24. {
    25.     long k=s[i];s[i]=s[j];s[j]=k;
    26.     k=t[i];t[i]=t[j];t[j]=k;
    27. }
    28. void quicksort(long d,long c)
    29. {
    30.     long l,r,m;
    31.     l=d;
    32.     r=c;
    33.     m=(d+c)/2;
    34.     if (d>=c) return;
    35.     do
    36.     {
    37.         while (s[l]<s[m]) l++;
    38.         while (s[r]>s[m]) r--;
    39.         if (l<=r)
    40.         {
    41.             if ((s[l]<s[r])||((s[l]==s[r])&(t[l]<t[r]))) swap(l,r);
    42.             l++;r--;
    43.         }
    44.     }
    45.     while (l<r);
    46.     if (d<r) quicksort(d,r);
    47.     if (l<c) quicksort(l,c);
    48. }
    49. //-----------Binary Index Tree------------
    50. void init_algo()
    51. {
    52.     long i;
    53.     for (i=0;i<n;i++) d[i]=0;
    54. }
    55. long getrs(long node)
    56. {
    57.     long i=node,max=0;
    58.     while (i>0)
    59.     {
    60.         max=(d[i]>max)?d[i]:max;
    61.         i-=(i&(-i));
    62.     }
    63.     return max;
    64. }
    65. void setvalue(long node,long delta)
    66. {
    67.     long i=node;
    68.     while (i<=m)
    69.     {
    70.         d[i]+=delta;
    71.         i+=(i&(-i));
    72.     }
    73. }
    74. void process()
    75. {
    76.     long i,max;
    77.     for (i=n-1;i>=0;i--)
    78.     {
    79.         max=getrs(t[i]);
    80.         setvalue(t[i],(max+1-d[t[i]]));
    81.     }
    82. }
    83. //----------------------------------------
    84. void output()
    85. {
    86.     cout<<getrs(m);
    87. }
    88.  
    89. int main()
    90. {
    91.     input();
    92.     quicksort(0,n-1);
    93.     init_algo();
    94.     process();
    95.     output();
    96.    
    97.     return 0;  
    98. }
    Ngày mai ra sao cũng chẳng biết nữa
    Mà có ra sao thì cũng chả sao

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

  1. Bài tập C giải thuật nhập vào số nguyên n in ra n số nguyên tố đầu tiên?
    Gửi bởi LTC trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 48
    Bài viết cuối: 25-04-2013, 07:40 PM
  2. thuật toán tìm số nguyên tố nhỏ nhất có n chữ số
    Gửi bởi phamhongcong1708 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 6
    Bài viết cuối: 22-10-2011, 10:10 PM
  3. Lập trình C xin code cài đặt thuật toán sàng nguyên tố để liệt kê các số nguyên tố 2->480000
    Gửi bởi ngocdung_088 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 23
    Bài viết cuối: 06-12-2010, 11:53 PM
  4. Thuật toán tìm số nguyên tố nhanh nhất?
    Gửi bởi MYLOVEPHUCLAM trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 3
    Bài viết cuối: 16-10-2010, 05:29 PM
  5. Trả lời: 16
    Bài viết cuối: 16-07-2010, 06:44 AM

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