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

Đề tài: Bài toán Nước đọng trên VNOI viết bằng C. Chạy không đúng...

  1. #1
    Ngày gia nhập
    10 2011
    Bài viết
    17

    Mặc định Bài toán Nước đọng trên VNOI viết bằng C. Chạy không đúng...

    Mấy pro ơi,cho hỏi cái.Đây là bài Nước đọng ( V11WATER ) trên VNOI.Đề bài là:

    [B]Năm 2011, tình trạng ngập lụt trong thành phố trở lên nghiêm trọng hơn. Vì vậy, mọi người quyết định xây dựng hệ thống mái che cho toàn thành phố.

    Mái che có bề rộng là N, được chia làm N phần có độ dài như nhau. Độ cao của mỗi phần là h1, h2, ..., hn. Khi trời mưa, một phần nước sẽ đọng lại trên mái và một phần sẽ thoát ra ngoài theo hai bên trái và phải của mái che. Do đó, thành phố sẽ không phải chịu cảnh mưa lụt như trước.
    Nhằm mục đích bảo trì mái che, bạn cần viết chương trình tính lượng nước lớn nhất có thể đọng lại trên mái che.

    Input
    - Dòng đầu ghi số N. (1 <= N <= 100000)
    - Dòng sau ghi N số tự nhiên h1, h2, ..., hn. (1 <= hi <= 100000)
    - Output
    - Gồm một số duy nhất thể hiện lượng nước tìm được.
    - Giới hạn
    50% số test có N <= 1000.

    Example
    Input:
    5
    1 3 1 2 3
    Output:
    3

    Đây là bài của mình.Không hiểu vì sao khi gửi nó chỉ cho mình có 10đ. @@!!
    Thuật toán của mình là:tìm cột cao nhất.Rồi từ cột cao nhất đó chia làm 2 phía.Đi đến đâu thì cộng lượng nước đọng lại trên đường.Các pác xem hộ em nhé.Thks trc
    C Code:
    1. #include<stdio.h>
    2. int n;
    3. int a[100000];
    4. void Enter()
    5. {
    6.      int i;
    7.      scanf("%d",&n);
    8.      for (i=0;i<n;i++)
    9.          scanf("%d",&a[i]);
    10. }
    11. int Search(int x, int y)
    12. {
    13.     int i,j,max;
    14.     max = a[x];
    15.     j=x;
    16.     for (i=x+1;i<=y;i++)
    17.         if ( a[i] > max )
    18.         {
    19.              max = a[i];
    20.              j = i;
    21.         }
    22.     return j;
    23. }
    24. int F(int m,int v)
    25. {
    26.     int k,s=0;
    27.     for (k=m+1;k<=v;k++)
    28.         s+=a[k];
    29.     return (v-m+1)*a[v] - s - a[v];
    30. }
    31. int Right(int m)
    32. {
    33.     int x,s=0,l;
    34.     l=m;
    35.     while ( l!=n-1 )
    36.     {
    37.         x = Search(l+1,n-1);
    38.         s+=F(l,x);
    39.         l=x;
    40.     }
    41.     return s;
    42. }
    43. int Left(int m)
    44. {
    45.     int l,x,s=0;
    46.     l=0;
    47.     while ( l!=m-1 )
    48.     {
    49.         x=Search(l+1,m-1);
    50.         s+=F(l,x);
    51.         l=x;
    52.     }
    53.     return s;
    54. }
    55. int main()
    56. {
    57.     int x;
    58.     Enter();
    59.     x = Search(0,n-1);
    60.     printf("%d",Right(x)+Left(x));
    61.     return 0;
    62. }

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

    Mình lười đọc quá, bạn xem code của mình đi
    C++ Code:
    1. #include<iostream>
    2. #define nm 100001
    3. using namespace std;
    4. int n,m;
    5. int a[nm],l[nm],r[nm];
    6. long long res=0;
    7. int main()
    8. {
    9.     scanf ("%d",&n);
    10.     for (int i=1;i<=n;i++)scanf ("%d",&a[i]);
    11.     m=a[1];
    12.     for (int i=2;i<=n;i++)l[i]=m,m=max(m,a[i]);
    13.     m=a[n];
    14.     for (int i=n-1;i>=1;i--)r[i]=min(l[i],m),m=max(m,a[i]);
    15.     for (int i=2;i<n;i++)
    16.     if (r[i]>a[i])res+=r[i]-a[i];
    17.     printf ("%lld",res);
    18.     return 0;
    19. }

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

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

    Ax,mình có cần bạn copy code đâu ==".Nói cho mình ý tưởng của bạn thôi..
    Mình đã fix lại bài của mình nhưng vẫn chỉ đc 50 :(.Chắc là do có bộ test làm 100000 nên phép tính với hàm F1 và F2 của mình bị tràn số.Có ai có cách khắc phục ko?
    C Code:
    1. #include<stdio.h>
    2. int n;
    3. int a[100000];
    4. void Enter()
    5. {
    6.      int i;
    7.      scanf("%d",&n);
    8.      for (i=0;i<n;i++)
    9.          scanf("%d",&a[i]);
    10. }
    11. int Search(int x, int y)
    12. {
    13.     int i,j,max;
    14.     max = a[x];
    15.     j=x;
    16.     for (i=x+1;i<=y;i++)
    17.         if ( a[i] > max )
    18.         {
    19.              max = a[i];
    20.              j = i;
    21.         }
    22.     return j;
    23. }
    24. int BackSearch(int x,int y)
    25. {
    26.     int i,j,max;
    27.     max = a[y-1];
    28.     j=y-1;
    29.     for (i=y-2;i>=x;i--)
    30.         if ( a[i] > max )
    31.         {
    32.              max = a[i];
    33.              j = i;
    34.         }
    35.     return j;
    36. }
    37. int F1(int m,int v)
    38. {
    39.     int k,s=0;
    40.     for (k=m+1;k<=v;k++)
    41.         s+=a[k];
    42.     return (v-m+1)*a[v] - s - a[v];
    43. }
    44. int F2(int m,int v)
    45. {
    46.     int k,s=0;
    47.     for (k=v-1;k>=m;k--)
    48.         s+=a[k];
    49.     return (v-m+1)*a[m] - s - a[m];
    50. }
    51. int Right(int m)
    52. {
    53.     int x,s=0,l;
    54.     l=m;
    55.     while ( l!=n-1 )
    56.     {
    57.         x = Search(l+1,n-1);
    58.         s+=F1(l,x);
    59.         l=x;
    60.     }
    61.     return s;
    62. }
    63. int Left(int m)
    64. {
    65.     int l,x,s=0;
    66.     l=m;
    67.     while ( l!=0 )
    68.     {
    69.         x=BackSearch(0,l);
    70.         s+=F2(x,l);
    71.         l=x;
    72.     }
    73.     return s;
    74. }
    75. int main()
    76. {
    77.     int x;
    78.     Enter();
    79.     x = Search(0,n-1);
    80.     printf("%d",Right(x)+Left(x));
    81.     return 0;
    82. }

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

    sorry vì mình ko đọc kỹ yêu cầu của bạn

    Mình dùng mảng từ 1->n
    - Thuật toán của mình là với mỗi i > 1 mình tìm l[i] là giá trị lớn nhất bên trái i
    - Với mỗi i< n mình tìm r[i] là giá trị nhỏ nhất trong (l[i],giá trị lớn nhất bên phải i)
    - for (2->n) nếu a[i]>r[i] cộng r[i]-a[i] vào kết quả
    - Lưu ý là kết quả có thể lớn hơn số 32 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
    10 2011
    Bài viết
    17

    Thks nhiều nha.Mình hiểu rồi.CODE của bạn tối ưu thật đó

  6. #6
    Ngày gia nhập
    12 2009
    Nơi ở
    The country of happiness
    Bài viết
    182

    Mặc định Bài toán Nước đọng trên VNOI viết bằng C. Chạy không đúng...

    bài này mình nộp mãi vẫn 50 điểm, lúc đầu ko hiểu tại sao. Sau hóa ra là do làm bên codeforces phải in là "%I64d", sang spoj cũng in như thế nên bị WA, phải in là "%lld" mới AC được .
    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viết
    Ôi skill của mình đã đạt đến hàng tuyệt đỉnh
    Không chỉ ăn, tắm, đi lại có thể code
    Mà giờ đã mình có thể code cả khi ngủ. Code tạm vào buffer của não, lúc nào dậy chỉ việc viết ra một cách trôi chảy không lưỡng lự.
    PS: Nếu ngủ dài rảnh rảnh có thể debug luôn, dậy chỉ việc build ?
    Trích dẫn Nguyên bản được gửi bởi vietanh8286 Xem bài viết
    Lập trình viên giỏi là lập trình viên có vợ

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

  1. Bài tập C Thiết kế mạch điện ghép nối mạch phát còi báo động qua cổng LPT. Code viết bằng C chạy không đúng như muốn!
    Gửi bởi mottraitims trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 18-05-2012, 04:33 AM
  2. ajax chạy trên ie thì đúng mà trên chorme lại chạy sai
    Gửi bởi tuanngocpt trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 6
    Bài viết cuối: 20-02-2012, 11:45 PM
  3. Hàm xuatmang của mình viết đúng nhưng lại chạy sai, mọi người vô xem giúp mình nha ..!!
    Gửi bởi thanhlinh.vietnam trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 14
    Bài viết cuối: 09-08-2011, 09:26 PM
  4. Viết lại hàm qsort chạy không đúng?
    Gửi bởi j3amboo trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 05-06-2011, 01:22 PM
  5. ASP.NET tinyMCE không chạy đúng trên google chrome, làm sao sửa?
    Gửi bởi minhdv85 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 05-03-2010, 10:08 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