PDA

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



minhtuan.a0
21-11-2011, 08:57 PM
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 :)

#include<stdio.h>
int n;
int a[100000];
void Enter()
{
int i;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
}
int Search(int x, int y)
{
int i,j,max;
max = a[x];
j=x;
for (i=x+1;i<=y;i++)
if ( a[i] > max )
{
max = a[i];
j = i;
}
return j;
}
int F(int m,int v)
{
int k,s=0;
for (k=m+1;k<=v;k++)
s+=a[k];
return (v-m+1)*a[v] - s - a[v];
}
int Right(int m)
{
int x,s=0,l;
l=m;
while ( l!=n-1 )
{
x = Search(l+1,n-1);
s+=F(l,x);
l=x;
}
return s;
}
int Left(int m)
{
int l,x,s=0;
l=0;
while ( l!=m-1 )
{
x=Search(l+1,m-1);
s+=F(l,x);
l=x;
}
return s;
}
int main()
{
int x;
Enter();
x = Search(0,n-1);
printf("%d",Right(x)+Left(x));
return 0;
}

hunterphu
21-11-2011, 10:10 PM
Mình lười đọc quá, bạn xem code của mình đi :)

#include<iostream>
#define nm 100001
using namespace std;
int n,m;
int a[nm],l[nm],r[nm];
long long res=0;
int main()
{
scanf ("%d",&n);
for (int i=1;i<=n;i++)scanf ("%d",&a[i]);
m=a[1];
for (int i=2;i<=n;i++)l[i]=m,m=max(m,a[i]);
m=a[n];
for (int i=n-1;i>=1;i--)r[i]=min(l[i],m),m=max(m,a[i]);
for (int i=2;i<n;i++)
if (r[i]>a[i])res+=r[i]-a[i];
printf ("%lld",res);
return 0;
}

minhtuan.a0
21-11-2011, 10:32 PM
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?

#include<stdio.h>
int n;
int a[100000];
void Enter()
{
int i;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
}
int Search(int x, int y)
{
int i,j,max;
max = a[x];
j=x;
for (i=x+1;i<=y;i++)
if ( a[i] > max )
{
max = a[i];
j = i;
}
return j;
}
int BackSearch(int x,int y)
{
int i,j,max;
max = a[y-1];
j=y-1;
for (i=y-2;i>=x;i--)
if ( a[i] > max )
{
max = a[i];
j = i;
}
return j;
}
int F1(int m,int v)
{
int k,s=0;
for (k=m+1;k<=v;k++)
s+=a[k];
return (v-m+1)*a[v] - s - a[v];
}
int F2(int m,int v)
{
int k,s=0;
for (k=v-1;k>=m;k--)
s+=a[k];
return (v-m+1)*a[m] - s - a[m];
}
int Right(int m)
{
int x,s=0,l;
l=m;
while ( l!=n-1 )
{
x = Search(l+1,n-1);
s+=F1(l,x);
l=x;
}
return s;
}
int Left(int m)
{
int l,x,s=0;
l=m;
while ( l!=0 )
{
x=BackSearch(0,l);
s+=F2(x,l);
l=x;
}
return s;
}
int main()
{
int x;
Enter();
x = Search(0,n-1);
printf("%d",Right(x)+Left(x));
return 0;
}

hunterphu
21-11-2011, 10:42 PM
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ả :D
- Lưu ý là kết quả có thể lớn hơn số 32 bit :)

minhtuan.a0
22-11-2011, 08:36 AM
Thks nhiều nha.Mình hiểu rồi.CODE của bạn tối ưu thật đó (=D)>

tiendaotd
22-11-2011, 01:42 PM
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 .