给出n个柱子一字排开,并且整体倾斜angle角度.向左为正,向右为负.求最多的积水量。
思路:
找出倾斜后最高柱子，再分求再边的水。有个小trick，水位刚好在某柱子中间：
以下来自官解题报告：
为使考虑简单,当angle为负时,将n个柱子颠倒顺序,angle取绝对值,得到的结果实际上是一样的.因此只需考虑向左倾斜
同时,为了避免大量坐标变换,柱子倾斜,其实就是地平线\水平面倾斜,因此,柱子不变,柱子左下角设为原点.从原点往右下角拉一条线出来作为倾斜的地平线.
接下来,计算每根柱子顶端与地平线的最大垂直距离.那么,水体肯定在2根距离较高的,柱子中间.称这2根柱子匹配
找到距离最大的柱子,那么,对于左侧的柱子,肯定与右边最近的,与地平线距离大于等于本身的柱子相匹配.对于右侧的柱子,肯定与左边某柱子匹配.因此做向左向右两次循环即可找出所有匹配.
我的代码：
[cpp]
/*
program:hdu_4368
author:BlackAndWhite
*/
#include
#include
#define eps 1e-5
#define PI 3.1415926535897932384626
int n,a[10001];
double angle;
int i,j,k,maxtop;
double dis[10001],t,top,ans,low,h;
int main()
{
while(~scanf("%d%lf",&n,&angle))
{
if(angle<-eps) for(i=n-1;i>=0;i--) scanf("%d",&a[i]);
else for(i=0;i
angle=PI*angle/180.0;
t=-1;ans=0;
for(i=0;i
dis[i]=((i+1)*tan(angle)+a[i]*1.0)/sqrt(tan(angle)*tan(angle)+1);
if(t
for(i=0;i
top=a[i];
{
if(dis[j]>dis[i]+eps)
{
if(dis[j]-sin(angle)>dis[i]+eps)
{
top-=(j-i-1)*1.0*tan(angle);
ans+=(j-i-1)*(j-i-1)*0.5*tan(angle);
}
else//trick，水刚好某个柱子了中间
{
top-=(a[i]-a[j])*1.0;
ans+=(a[i]-a[j])*(a[i]-a[j])*0.5/tan(angle);
}
for(k=i+1;k
i=j-1;
break;
}
}
}
for(i=n-1;i>maxtop;i--)//右边，相对简单些，没有trick
{
for(j=i-1;j>=maxtop;j--)
{
h=i-j;
low=h*tan(angle)-(a[j+1]-a[i]);
top=(h-1)*tan(angle)-(a[j+1]-a[i]);
ans+=(top+low)/2.0;
if(dis[j]>dis[i]+eps)
break;
}
i=j+1;
}
printf("%.2lf\n",ans);
}
return 0;
}
作者：q411307827