題意：
給出n個柱子一字排開,並且整體傾斜angle角度.向左為正,向右為負.求最多的積水量。
思路:
找出傾斜後最高柱子，再分求再邊的水。有個小trick，水位剛好在某柱子中間：
以下來自官解題報告：
為使考慮簡單,當angle為負時,將n個柱子顛倒順序,angle取絕對值,得到的結果實際上是一樣的.因此只需考慮向左傾斜
同時,為了避免大量坐標變換,柱子傾斜,其實就是地平線\水平面傾斜,因此,柱子不變,柱子左下角設為原點.從原點往右下角拉一條線出來作為傾斜的地平線.
接下來,計算每根柱子頂端與地平線的最大垂直距離.那麼,水體肯定在2根距離較高的,柱子中間.稱這2根柱子匹配
找到距離最大的柱子,那麼,對於左側的柱子,肯定與右邊最近的,與地平線距離大於等於本身的柱子相匹配.對於右側的柱子,肯定與左邊某柱子匹配.因此做向左向右兩次循環即可找出所有匹配.
我的代碼：
[cpp]
/*
program:hdu_4368
author:BlackAndWhite
*/
#include<stdio.h>
#include<math.h>
#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<n;i++) scanf("%d",&a[i]);
if(angle<-eps) angle=-angle;//只考慮向左傾斜
angle=PI*angle/180.0;
t=-1;ans=0;
for(i=0;i<n;i++)
{
dis[i]=((i+1)*tan(angle)+a[i]*1.0)/sqrt(tan(angle)*tan(angle)+1);
if(t<dis[i]){t=dis[i];maxtop=i;}//找離地面最高的柱子
}
for(i=0;i<maxtop;i++)//最高柱子的前面
{
top=a[i];
for(j=i+1;j<=maxtop;j++)
{
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<j;k++)
ans+=(top-a[k])*1.0;
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
