纪中10日 2313. 动态仙人掌
(File IO): input:dinosaur.in output:dinosaur.out
时间限制: 1500 ms 空间限制: 524288 KB 具体限制
题目描述
沙雕游戏……反正我没玩过……
输入
输出
样例输入
数据范围限制
Solution
考试时想的是对的
为什么就是没有分呢？
首先看看仙人掌有几种情况
situation1
两个比较分开的仙人掌……
小恐龙按照这样走（跳），并没有什么特殊操作。这时的最高高度是两个仙人掌中最高的高度。
situation2
两个靠的比较近的仙人掌……
先看第一个，为了高度尽量小，当然选择擦边跳了
但是恐龙只有落地才能跳呀……要是它跳完第一个就落地，再起跳，一定会装上第二个仙人掌的！
所以它只能一次性的跳过两个仙人掌……
求最高点：
设第一个的高度为a，第二个的高度为b，两个之间的距离为c；
标点
解：
因为△ABC是直角等腰三角形
所以AD=DC=a
同理可得：
EG=FG=b
所以AF=AD+DG+GF=a+b+c
延长AB，EF，交于H点
△AHF亦为直角等腰三角形
所以AH=HF=AF/2=(a+b+c)/2
那么就可以把两个仙人掌合成一个更高的了
Code
#include<iostream>//不想OI一场空，千万别用万能头
#include<algorithm>//快排sort()
#include<cstdio>//能不用cin就不用
#include<cstring>
#include<map>
#include<vector>
#define IL inline
using namespace std;
IL void fin(){freopen("dinosaur.in","r",stdin);}
IL void fout(){freopen("dinosaur.out","w",stdout);}
IL void fio()
{
fin();
fout();
} struct node{
double p;
double h;
}din[];
bool cmp(node ta,node tb)
{
return ta.p<tb.p;
}
int n,tp,th,maxn;
double ans=-;
int main()
{
// fio();
cin>>n;
for(int i=;i<n;i++)
{
scanf("%d%d",&tp,&th);
din[i].p=tp;
din[i].h=th;
ans=max(ans,(double)din[i].h);
if(din[i].p-din[i].h<){
cout<<"-1\n";
return ;
}
}
sort(din,din+n,cmp);
int a,b,c;
for(int i=;i<n-;i++)
{
c=din[i+].p+din[i].p;
a=din[i].h;
b=din[i+].h;
if(c>=a+b)
{
ans=max(ans,(double)max(a,b));
}
else
{
ans=max(ans,(a+b+c)/2.0);
din[i+].p=(a+din[i].p+din[i+].p-b)/2.0;
din[i+].h=(a+b+c)/2.0;
}
}
printf("%.1lf",ans);
return ;
}
Code std
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct cly
{
int longn,left,right;
}a[];
double ans;
int n,p[],h[],l,r,i;
bool cmd(cly x,cly y)
{
return x.left<y.left;
}
int main()
{
// freopen("dinosaur.in","r",stdin);
// freopen("dinosaur.out","w",stdout);
cin>>n;
for(i=;i<=n;i++)
{
scanf("%d%d",p+i,h+i);
a[i]=(cly){h[i],p[i]-h[i],p[i]+h[i]};
}
sort(a+,a++n,cmd);
if(a[].left<)
{
cout<<"-1";
return ;
}
l=a[].left;
r=a[].right;
i=;
while(i<n)
{
if(r<=a[i+].left)
{
ans=max(ans,1.0*(r-l)/);
i++;
l=a[i].left;
r=a[i].right;
}
else if(r>=a[i+].right)
{
i++;
}
else
{
i++;
r=a[i].right;
}
}
ans=max(ans,1.0*(r-l)/);
printf("%.1lf",ans);
return ;
}