P3382 【模板】三分法

P3382 【模板】三分法

提交 9.62k
通过 5.68k
时间限制 100ms
内存限制 125.00MB
题目提供者 HansBug
历史分数100

提交记录

标签

暂无标签
进入讨论版

相关讨论

 
查看讨论

推荐题目

 
查看推荐
 

展开

题目描述

如题,给出一个 NNN 次函数,保证在范围 [l,r][l, r][l,r] 内存在一点 xxx,使得 [l,x][l, x][l,x] 上单调增,[x,r][x, r][x,r] 上单调减。试求出 xxx 的值。

输入格式

第一行一次包含一个正整数 NNN 和两个实数 l,rl, rl,r,含义如题目描述所示。

第二行包含 N+1N + 1N+1 个实数,从高到低依次表示该 NNN 次函数各项的系数。

输出格式

输出为一行,包含一个实数,即为 xxx 的值。四舍五入保留 555 位小数。

输入输出样例

输入 #1
3 -0.9981 0.5
1 -3 -3 1
输出 #1
-0.41421

说明/提示

对于 100%100\%100% 的数据,7≤N≤137 \le N \le 137N13。

【样例解释】

如图所示,红色段即为该函数 f(x)=x3−3x2−3x+1f(x) = x^3 - 3 x^2 - 3x + 1f(x)=x33x23x+1 在区间 [−0.9981,0.5][-0.9981, 0.5][0.9981,0.5] 上的图像。

x=−0.41421x = -0.41421x=0.41421 时图像位于最高点,故此时函数在 [l,x][l, x][l,x] 上单调增,[x,r][x, r][x,r] 上单调减,故 x=−0.41421x = -0.41421x=0.41421,输出 −0.41421-0.414210.41421。

(Tip.l&r的范围并不是非常大ww不会超过一位数)

 

思路:

  求单峰极值可以想到模拟退火三分,和二分类比一下,二分需要一个中间点,三分需要两个中间点,就是三等分点然后根据求的是极大值还是极小值比较三分点并转移

CODE

 

 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 #define eps 1e-8
 4 
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 template<class T>inline void read(T &res)
 9 {
10     char c;T flag=1;
11     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
12     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
13 }
14 
15 namespace _buff {
16     const size_t BUFF = 1 << 19;
17     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
18     char getc() {
19         if (ib == ie) {
20             ib = ibuf;
21             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
22         }
23         return ib == ie ? -1 : *ib++;
24     }
25 }
26 
27 int qread() {
28     using namespace _buff;
29     int ret = 0;
30     bool pos = true;
31     char c = getc();
32     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
33         assert(~c);
34     }
35     if (c == '-') {
36         pos = false;
37         c = getc();
38     }
39     for (; c >= '0' && c <= '9'; c = getc()) {
40         ret = (ret << 3) + (ret << 1) + (c ^ 48);
41     }
42     return pos ? ret : -ret;
43 }
44 
45 int n;
46 double l,r;
47 double a[20];
48 
49 double f(double x) {//函数计算
50     double u = 1, p = 0;
51     for(int i = n; i >= 0; --i) {
52         p += u*a[i];
53         u *= x;
54     }
55     return p;
56 }
57 
58 double ts(double l, double r) {
59     while(l + eps < r) {
60         double lmid = l + (r-l)/3, rmid = r - (r-l)/3;
61         if(f(lmid) <= f(rmid)) {
62             l = lmid;
63         }
64         else {
65             r = rmid;
66         }
67     }
68     return r;
69 }
70 
71 int main()
72 {
73     memset(a, 0, sizeof(a));
74     scanf("%d",&n);
75     scanf("%lf%lf",&l, &r);
76 
77     for(int i = 0; i <= n; ++i) {
78         scanf("%lf", &a[i]);
79     }
80     printf("%.5f\n",ts(l,r));
81     return 0;
82 }
View Code

 

 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 #define eps 1e-8
 4 
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 template<class T>inline void read(T &res)
 9 {
10     char c;T flag=1;
11     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
12     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
13 }
14 
15 namespace _buff {
16     const size_t BUFF = 1 << 19;
17     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
18     char getc() {
19         if (ib == ie) {
20             ib = ibuf;
21             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
22         }
23         return ib == ie ? -1 : *ib++;
24     }
25 }
26 
27 int qread() {
28     using namespace _buff;
29     int ret = 0;
30     bool pos = true;
31     char c = getc();
32     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
33         assert(~c);
34     }
35     if (c == '-') {
36         pos = false;
37         c = getc();
38     }
39     for (; c >= '0' && c <= '9'; c = getc()) {
40         ret = (ret << 3) + (ret << 1) + (c ^ 48);
41     }
42     return pos ? ret : -ret;
43 }
44 
45 int n;
46 double l,r;
47 double a[20];
48 
49 double f(double x) {///多项式求值秦九韶算法把2n+1次乘法n次加法简化为n次乘法和n次加法
50     double u = 1, p = 0;
51     for(int i = n; i >= 0; --i) {
52         p += u*a[i];
53         u *= x;
54     }
55     return p;
56 }
57 
58 double ts(double l, double r) {
59     while(l + eps < r) {
60         double lmid = l + (r-l)/3, rmid = r - (r-l)/3;
61         if(f(lmid) <= f(rmid)) {
62             l = lmid;
63         }
64         else {
65             r = rmid;
66         }
67     }
68     return r;
69 }
70 
71 int main()
72 {
73     memset(a, 0, sizeof(a));
74     scanf("%d",&n);
75     scanf("%lf%lf",&l, &r);
76 
77     for(int i = 0; i <= n; ++i) {
78         scanf("%lf", &a[i]);
79     }
80     printf("%.5f\n",ts(l,r));
81     return 0;
8
全部评论

相关推荐

感觉这一周太梦幻了,就像一个梦,很不真实~~~感觉这个暑期,我的运气占了99成,实力只有百分之一4.15上午&nbsp;腾讯csig&nbsp;腾讯云部门,面完秒进入复试状态4.16下午&nbsp;美团优选供应链部门,4.18上午发二面4.17晚上&nbsp;阿里国际一面,纯拷打,面完我都玉玉了4.18下午&nbsp;阿里国际二面,是我们leader面的我,很轻松~~4.18晚上&nbsp;约了hr面4.19上午&nbsp;hr面,下午两点口头oc4.19晚上&nbsp;意向书说起来我的暑期好像一次都没挂过~~~~~难道我是天生面试圣体?----------------------------------------------------------------------六个月前,我还是0项目0刷题,当时想的是先把论文发出来再去找实习。结果一次组会,老师打破了我的幻想(不让投B会,只让投刊或者A)我拿头投啊!!!然后就开始物色着找实习,顺便做完了mit的6.s081,但是基本上还是没刷过题目-----------------------------------------------------------------------11月&nbsp;&nbsp;一次偶然的机会,面进了某个耳机厂的手环部门,大概是做嵌入式的,用的是CPP。12月&nbsp;莫名其妙拿到了国创的面试机会,0基础四天速成java基础!居然也给我面过了hhhhh,可能是面试没写题吧入职国创后的几个月,一直没活,天天搁那看剧,都快忘了还有暑期实习这回事了~~~~命运的齿轮在2.26开始转动,因为这一天美团开了,我开始慌了,因为那时的我什么都不会。lc,八股,sql全部是0进度。然后就开始了女娲补天,上班刷题,下班继续做之前的开源,顺便学一学八股。3月到现在,lc也刷到快200了,一天最多提交了47次~~~~~~~~~~八股根据别人的面经总结和博客,写了快十万字的笔记~~~~~~~~~~简历上的实习经历和开源,也努力去深挖了,写了几万字的记录~~~~~~所以面试的时候,基本上都能cover了,面试官问到的基础基本都会,不基础的我就把他往我会的地方引。结果好像还不错,基本上每个面试官评价都挺好的emmmmmmmm
投递阿里巴巴等公司10个岗位
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务