http://acm.hdu.edu.cn/showproblem.php?pid=5105
给定a，b，c，d，l，r，表示有一个函数f(x)=|a∗x3+b∗x2+c∗x+d|(L≤x≤R)，求函数最大值。
考虑极点可能有0~2个。在极值点处函数的单调性会发生变化，所以最大值一定就在区间边界和极值点上。所以求下l,r,极值点的函数大小然后取最大的即可。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
#define clr1(x) memset(x,-1,sizeof(x))
template<class T> T max(T a, T b, T c) {
return max(a, max(b, c));
}
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
const int modo = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int inf = 0x3fffffff;
const LL _inf = 1e18;
const int maxn = 55,maxm = 1<<12;
const double eps = 1e-9;
double A,B,C,D,l,r;
double cal(double x)
{
if(l <= x && x <= r)
return fabs(A*x*x*x + B*x*x + C*x + D);
return -1;
}
double solve(double a,double b,double c)
{
if(fabs(a) < eps){
if(fabs(b) < eps)
return -1;
return cal(-c/b);
}
double dta = b*b - 4*a*c;
if(fabs(dta) >= eps){
dta = sqrt(dta);
return max(cal((dta - b)/2/a) , cal((-dta - b)/2/a));
}
return -1;
}
int main()
{
while(~scanf("%lf%lf%lf%lf%lf%lf",&A,&B,&C,&D,&l,&r)){
double ans = max(cal(l),cal(r),solve(A*3,B*2,C));
printf("%.2lf
",ans);
}
return 0;
}绝对值的最大值就是函数最大值或者负的最小值的相反数，考虑用三分法，但是依然需要考虑l,r两点，不然会WA，谨记教训！
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
#define clr1(x) memset(x,-1,sizeof(x))
template<class T> T max(T a, T b, T c , T d) {
return max(max(a,d) , max(b, c));
}
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
const int modo = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int inf = 0x3fffffff;
const LL _inf = 1e18;
const int maxn = 55,maxm = 1<<12;
const double eps = 1e-9;
double a,b,c,d,l,r;
double cal(double x)
{
return a*x*x*x + b*x*x + c*x + d;
}
int main()
{
while(~scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&l,&r)){
double _l = l,_r = r;
while(l + eps < r){
double mid = (l+r)/2,rr = (mid + r)/2;
if(cal(rr) < cal(mid))
l = mid;
else
r = rr;
}
double ans1 = l;
l = _l,r = _r;
while(l + eps < r){
double mid = (l+r)/2,rr = (mid + r)/2;
if(cal(rr) > cal(mid))
l = mid;
else
r = rr;
}
double ans2 = l;
printf("%.2lf
",max(fabs(cal(_l)),fabs(cal(_r)),fabs(cal(ans1)),fabs(cal(ans2))));
}
return 0;
}