Curves
发布日期:2022-02-05 18:27:29 浏览次数:15 分类:技术文章

本文共 1696 字,大约阅读时间需要 5 分钟。

【题目描述】

明明做作业的时候遇到了n个二次函数Si(x)= ax2 + bx + c,他突发奇想设计了一个新的函数F(x) = max(Si(x)), i = 1...n.

明明现在想求这个函数在[0,1000]的最小值,要求精确到小数点后四位四舍五入。

【输入数据】

输入包含T 组数据 (T < 10) ,每组第一行一个整数 n(n ≤ 10000) ,之后n行,每行3个整数a (0 ≤ a ≤ 100), b (|b| ≤ 5000), c (|c| ≤ 5000) ,用来表示每个二次函数的3个系数,注意二次函数有可能退化成一次。

 

【输出数据】

每组数据一个输出,表示新函数F(x)的在区间[0,1000]上的最小值。精确到小数点后四位,四舍五入。

 

【样例输入】

2

1

2 0 0

2

2 0 0

2 -4 2

 

【样例输出】

0.0000

0.5000

 

【数据范围】

T < 10, n ≤ 10000 , 0 ≤ a ≤ 100,|b| ≤ 5000, |c| ≤ 5000

50%数据n ≤ 100

好吧 一开始想的是 F(x)肯定在某两个函数的交点处改变单调性

然后暴力枚举交点 O(n)验证是否为所有函数图象中最上面的的那个(在F(x)上)

然后事实证明可以过50分

但是自己没写啊啊啊啊啊啊啊啊啊

用随机写的 撒点 随机移动

结果一个点也没过!!!

下午重新改了改 突然发现 

数据范围中 a 没加绝对值!!!

这说明什么呢?

说明F(x)是一个向下凸的单峰函数!!!

然后就可以爬山算法啦

嫌爬山麻烦 就写了个三分。。。

话说对精度要求太高了 要1e-9才可过

估计是有的函数太“陡”了吧

丧心病狂!!!还好不是noip

#include
#include
#include
#include
using namespace std;double l,r,mid,midmid;double ymid,ymidmid;struct self{double x,y,w;}s[10011];int m,a,b,c,d;int casenum;double f(int i,double x){ return s[i].x*x*x+s[i].y*x+s[i].w;}double finduper(double i){ double ret=-999999999; for(int a=1;a<=m;a++) ret=max(ret,f(a,i)); return ret;}int main(){ freopen("curves.in","r",stdin); freopen("curves.out","w",stdout); scanf("%d",&casenum); while(casenum) { casenum--; scanf("%d",&m); for(a=1;a<=m;a++)scanf("%lf%lf%lf",&s[a].x,&s[a].y,&s[a].w); l=0;r=1000; while(l

另外附上二分的题解

本题的关键是二分答案。由于输出只要求精确到4位,我们可以二分结果。设结果为ans,对于二分得到的任何一个值mid,我们可以计算出每条二次函数值低于它的区间。如果mid < ans,那么刚才所说的那些区间的交集为空,如果mid > ans 那么刚才所说的那些区间的交集就不为空了。

所以现在我们只需要进行二分搜索答案ans,每次通过把数带入二次函数计算出每个二次函数所对应的区间,然后判断这些区间的交集是否为空即可。判断区间交集是否为空可以直接判断他们最左的右端点是否在最右的左端点右边即可。每次二分判断的时间复杂度为O(n),整个算法的时间复杂度为O(pn), p为二分的次数。

转载地址:https://blog.csdn.net/li412302070/article/details/13613649 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:洛谷 1485 火枪打怪
下一篇:COGS 1022 防线

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月13日 18时27分08秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java转换ab的值,查看新闻/公告--[整理]Java将AB1234形式的16进制字符串转换为10进制数值,考虑字节序的影响.... 2019-04-21
ui php h5,画出自己的UI组件的详情 2019-04-21
linux服务文件编写,linux编写systemd下服务脚本 2019-04-21
hdfs linux 目录是否存在,Linux中判断hdfs文件是否存在 2019-04-21
linux学习需要什么基础,学linux需要什么基础? 2019-04-21
linux vim编辑kconfig 无法wq,Linux-4.9.2内核在mini2440上的移植(三)——编译环境测试... 2019-04-21
高斯勒让德在c语言中的程序,c语言:用递归方法编写程序,求n阶勒让德多项式的值... 2019-04-21
c语言单片机电子时钟,新人求个51单片机的电子时钟汇编语言(C语言的还没学到)... 2019-04-21
c++语言文件流,C++文件流 2019-04-21
android 动态毛玻璃,Android毛玻璃背景效果简单实现代码 2019-04-21
android 按钮提示,的Android按钮工具提示 2019-04-21
iphone通讯录 android,3个方法,教你如何快速而又有效的将联系人从iPhone转移到安卓... 2019-04-21
android horizontalscrollview 滑动事件,ScrollView的滑动监听(以HorizontalScrollView为例) 2019-04-21
win7自定义html为桌面,Win7系统自定义桌面主题的方法 2019-04-21
单系统 台电x80pro_台电x80 pro (ID:E3E6)安装remix OS系统教程整理 2019-04-21
linux存储pdf伟岸_python的reportlab库介绍、制作pdf和作图 2019-04-21
安徽信息技术初中会考上机考试模拟_2020年中小学寒假、考试时间定下了! 2019-04-21
ubuntu 退出anaconda环境_从零开始深度学习第15讲:ubuntu16.04 下深度学习开发环境搭建与配置... 2019-04-21
稳定币usda是哪个发行的_武夷山币装帧款曝光,共4款设计,你喜欢哪款? 2019-04-21
可变车道怎么走不违章_走ETC竟比人工车道贵50%!交警:这3点不知道,吃亏的是自己... 2019-04-21