PYC#1欢乐赛第三题题解

发布时间:2016-12-11 6:44:32 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"PYC#1欢乐赛第三题题解",主要涉及到PYC#1欢乐赛第三题题解方面的内容,对于PYC#1欢乐赛第三题题解感兴趣的同学可以参考一下。

这里是比赛地址:http://tieba.baidu.com/p/2859693237,果然参赛神牛汇集。 第三题题目大意如下: 已知n条二次函数曲线Si(x)=aix^2+bix+ci(ai>=0),定义F(x)=max{Si(x)},求出F(x)在[0,1000]上的最小值。第一行为数据组数T。每组数据第一行位正整数n,以下n行每行包括3个整数a,b,c。对于每组数据,输出所要求的最小值,保留4位小数。T< 10, n ≤ 10000,0 ≤ a ≤ 100,|b| ≤ 5000, |c| ≤5000。 有点像数学+二分,开始我想二分x的,但发现函数众多,线索混乱,觉得这会有问题。 后来这道题经RXD大牛点拨,我有了一个绝妙的想法 :二分枚举答案f(x),并验证。比如,我们枚举的答案当前是k,那么我们在坐标系里划一道y=k的图像,这与n条函数图像可能会有交点。因为F(x)=max{Si(x)},,所以在【0...1000】范围内,y=k一定在最上面。设某一二次函数解析式y=ax^2+bx+c,它与直线的交点为方程ax^2+bx+c=k的根(因为0≤ a ,所以如果b^2-4*a*c<0,说明函数在直线上方,可以直接否决当前的K),而它在直线的下方的部分可以用x1<x<x2来表示(x1和x2是方程的根)。如果对于所有的函数,其在直线下方的解集存在于【0..1000】范围内(无论多少),说明当前的K是可行的。 时间效率:O(log2(P)*n)),其中p是你答案枚举的范围。(最好设的大一点)  然而,我交上去后,发现全WA了!! 后来经过我对数据的不断调试,发现如下两个问题。 (1)二分答案时如何确定边界。保留4位精度嘛,我原先用ok函数来判断。如果ok(l)=ok(r),就退出。 long ok(double k) { if (long(k*100000)%10>4) return(long(k*10000+1)); return (long(k*10000)); } 即如果枚举的l和r小数点后四位相同,就退出。 但是这会有问题 ,比如l=0.999,并无限接近1;r=1.001,也无限接近1。这样,即使二分到很后面,如l=0.99999999,r=1.00000001,他们的后四位仍然不同。 后来我发现一个更简单的判断方法,即(r-l<=0.00001 (5位))  (2)a可能为0,即某一函数可能不是二次函数,而是一次函数。 因为在求根公式中,a被当做了除数,这样除0的话就会爆掉。因此,对于一次函数,要简单处理一下(其实更容易) 以下附代码: #include<stdio.h> #include<cmath> using namespace std; long a[10001],b[10001],c[10001],i,j,t,n,oo=2000000000; //oo被视为无限大 double ans; bool check(double h) { long i;double x1,x2,t,start1=0,start2=1000,p; for (i=1;i<=n;i++) { p=b[i]*b[i]-4*a[i]*(c[i]-h); if (p<0) returnfalse;p=sqrt(p); if (a[i]==0) { if(b[i]>0){x1=-oo;x2=(h-c[i])/b[i];} else if(b[i]<0){x1=(h-c[i])/b[i];x2=oo;} else if (c[i]>h) return false; else { x1=-oo;x2=oo;} } else { x1=(-b[i]-p)/a[i]/2; x2=(-b[i]+p)/a[i]/2; } if (start2<x1||x2<start1) returnfalse; if (x1>start1) start1=x1;if (x2<start2)start2=x2; } return true; } double erfen(double l,double r) { double mid=(l+r)/2; if ((r-l)<=1e-5) return mid; if (check(mid)) return erfen(l,mid); return erfen(mid,r); } int main() { freopen("pyc.in","r",stdin); freopen("pyc.out","w",stdout); scanf("%ld",&t); for (j=1;j<=t;j++) { scanf("%ld",&n); for (i=1;i<=n;i++) scanf("%ld%ld%ld",&a[i],&b[i],&c[i]); ans=erfen(0,10000); //当然再开大一点也可以,只是不要超时了 printf("%.4f\n",ans); } }最后提出一个意见,第10组数据中出现了a<0,使我的程序出错,请PYC及时纠正。O(∩_∩)O~~

上一篇:java static关键字
下一篇:VMware Workstation虚拟机网络连接杂记、给Windows虚拟机配置固定IP

相关文章

相关评论