三分
不严谨的总结
参考资料:
洛谷 P3382(三分查找凹点和凸点)
AcWing 104. 货仓选址(三分法)
三分法求函数极值(复习)
凸函数
while(r - l > eps)
{
double mid = (l + r) / 2;
double mmid = (mid + r) / 2;
if(check(mid) > check(mmid) ) r = mmid;
else l = mid;
}
凹函数
while(l < r - 1) // l < r - 1 ?
{
int mid = (l + r) / 2;
int mmid = (mid + r) / 2;
if(check(mid) > check(mmid)) l = mid;
else r = mmid;
}
- 凸函数 P3382 【模板】三分法
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 15;
#define eps 1e-7
int n;
double l,r;
double a[N]; // 系数
double check(double x)
{
double ans = 1, sum = 0;
for(int i = n + 1 ;i >= 1;i -- )
{
sum += ans * a[i];
ans *= x;
}
return sum;
}
int main()
{
cin >> n >> l >> r;
for(int i = 1;i <= n + 1;i ++ ) cin >> a[i];
while(r - l > eps)
{
double mid = (l + r) / 2;
double mmid = (mid + r) / 2;
if(check(mid) > check(mmid) ) r = mmid;
else l = mid;
}
printf("%.5lf",l);
return 0;
}
- 凹函数 104. 货仓选址
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int check(int x)
{
int res = 0;
for(int i = 0 ;i < n;i ++ ) res += abs(a[i] - x);
return res;
}
int main()
{
cin >> n;
for(int i = 0 ;i < n;i ++ ) cin >> a[i];
sort(a, a + n);
int l = a[0], r = a[n - 1];
while(l < r - 1) // l < r - 1 ?
{
int mid = (l + r) / 2;
int mmid = (mid + r) / 2;
if(check(mid) > check(mmid)) l = mid;
else r = mmid;
}
cout << min(check(l),check(r)) << endl;
return 0;
}
这是一道凹函数的例题,感觉比货舱选址更好些,可以考虑加上
另外附上自己的题解