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~~

上一篇:ssky-keygen + ssh-copy-id 无密码登陆远程LINUX主机


下一篇:20175126Apollo 20175126《Java程序设计》结队编程项目——四则运算