本文最后更新于 1059 天前，其中的信息可能已经有所发展或是发生改变。
1.三分法
在对区间做二分查找之前，我们要保证这个区间是有序的，二分法适用于单调函数。对于非单调函数，二分法就不适用了，需要使用一种新的方法——三分法。
三分法首先把待求区间分成三份
mid1=L+(R-L)/3
mid2=R-(R-L)/3
比较f(mid1)和f(mid2)谁更靠近极值，若f(mid1)更靠近极值，则将右区间改为mid2，若f(mid2)更靠近极值，则将左区间改为mid1，再次计算mid1和mid2。重复以上过程，直至L+eps>R（eps为设置的误差值）
三分法适用于单峰函数的求极值。
#define eps 10e-6
double f() {} //计算题目所需要的值
while(l+eps<r)
{
m1=l+(r-l)/3;
m2=r-(r-l)/3;
v1=f(m1);
v2=f(m2);
if(v1<v2)l=m1;
else r=m2;
}
例题：
派件问题-2
描述
罗少有 n 件物品需要派送，但是他太懒了，于是他想找若干个小弟来帮忙。
已知每个小弟的服务费由两部分组成：跑腿费 s 元 + t * t 元，其中 t 代表这个小弟携带的物品件数。
请问罗少至少需要花多少钱才能把这 n 件物品派送完。
输入
第一行是一个正整数 T 代表测试案例的数量。（1 <= T <= 10000)
每组案例包含两个正整数 n、s 含义如描述所述。
对于 50% 的样例有 1 <= n、s <= 1e3。
对于 100% 的样例有 1 <= n、s <= 1e6。
输出
针对每组案例，输出罗少至少需要花多少钱，然后换行。
样例输入
2
2 1
2 3
样例输出
4
7
我们用dfs跑一遍较小的数据之后发现，最优解中每个小弟携带的物品都基本相同。也就是说，n件物品，分配给x个小弟，每个小弟得到n/x件物品时得到最优解。
但是还有一个小小的问题，n/x有余数怎么办？
很简单，让n%x个小弟多带一件物品就好了。也就是让(x-n%x)个小弟携带n/x件物品，让n%x个小弟携带n/x+1件物品。
据此，我们可以列出这样一个式子：
$ans=(x-n \bmod x)*(s+(\frac{n}{x})*(\frac{n}{x}))+(n \bmod i)*(s+(\frac{n}{x}+1)* (\frac{n}{x}+1))$
ll f(ll x)
{
ll unit = n / x;//(n/x)算出每件物品的单价，也是(x-surplus)个小弟携带的物品件数
ll surplus = n % x;//剩余的小弟多携带一件
ll ans = (x - surplus) * (s + unit * unit) + surplus * (s + (unit + 1) * (unit + 1));
return ans;
}
重点来了：写出f(x)之后，直接套上三分法的代码就可以了。但是这题有点特殊，这题求出的极值点须为整数，所以我们要优化一下三分法的代码。
ll SanFen(ll l, ll r) //找凸点
{
while (l<r-1)
{
ll mid1 = l + (r - l) / 3;
ll mid2 = r - (r - l) / 3;
if (mid1 == l && mid2 == r)break;//增加的代码
if (f(mid1) < f(mid2))
r = mid2;
else
l = mid1;
}
ll minn = LLONG_MAX;//以下均为增加的代码
for (ll i = l; i <= r; i++)//求出极值点所在区间
{
ll temp = f(i);
if (temp < minn)minn = temp;
}
return minn;
}
上述代码比之前给出的模板代码增添了几行，为什么呢？把if (mid1 == l && mid2 == r)break;这行注释之后可以发现，程序进入了死循环中。因为本题中变量类型均为long long，而整数相除的误差又相对较大，所以程序运行到最后mid1永远等于l，mid2永远等于r。此时L、R差值较小，[L,R]为极值点所在区间，所以可以跳出循环用for循环在求出的极值点所在的区间去尝试求出极值。
完整代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll n, ll s, ll x)
{
ll unit = n / x, surplus = n % x;
ll sum = (x - surplus) * (s + unit * unit) + surplus * (s + (unit + 1) * (unit + 1));
return sum;
}
ll SanFen(ll l, ll r, ll n, ll s) //找凸点
{
while (1)
{
ll mid1 = l + (r - l) / 3;
ll mid2 = r - (r - l) / 3;
if (mid1 == l && mid2 == r)break;
if (f(n, s, mid1) < f(n, s, mid2))
r = mid2;
else
l = mid1;
}
ll minn = LLONG_MAX;
for (ll i = l; i <= r; i++)
{
ll temp = f(n, s, i);
if (temp < minn)minn = temp;
}
return minn;
}
int main()
{
int T;
cin >> T;
while (T--)
{
ll n, s;
scanf("%lld%lld", &n, &s);
ll minn = SanFen(1, n, n, s);
cout << minn << endl;
}
return 0;
}
再来看下一题
勇者斗恶龙-3
一位勇者遇到了一条恶龙，紧接着双方开始了回合制战斗。在每一个回合中，勇者都有两种选择：1、使自己的攻击力增加 b 点。2、攻击一次恶龙。
已知勇者的初始攻击力为 a，恶龙的血量为 c，当恶龙的血量降低到 0 或更低时，勇者获胜。
勇者不想因为与恶龙战斗浪费太多的时间，所以请你帮忙算一下，勇者至少需要几个回合才能杀死恶龙。
输入
第一行是一个正整数 T 代表测试案例的数量。(1 <= T <= 1000)
每组案例包含三个正整数 a、b、c 含义如描述所述。
对于 33% 的数据 abc 均小于等于 1e3。
对于 66% 的数据 abc 均小于等于 1e9。
对于 100% 的数据 abc 均小于等于 1e18。
输出
针对每组案例，输出勇者获胜至少需要的回合数，然后换行。
样例输入
1
2 2 10
样例输出
4
HINT
勇者可以先用一回合增加攻击力到 4 点，然后再用三回合攻击恶龙。
当然他也可以先用两回合增加攻击力到 6 点，然后再用两回合攻击恶龙。
首先列出计算公式。可以很容易推出先增加攻击力再攻击恶龙。所以设增加攻击力次数为x，公式为$\frac{c}{a+b*x}+x$
ll f(ll x)
{
ll sum = c / (a + b * x) + x;
if (c % (a + b * x))sum++;
return sum;
}
随便创造了一个很大的数据，画图看看效果。（图为函数部分图像）
很明显存在一个极值，直接套整数三分公式：
挖坑代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;
ll f(ll x)
{
ll sum = c / (a + b * x) + x;
if (c % (a + b * x))sum++;
return sum;
}
ll SanFen(ll l, ll r) //找凸点
{
while (l < r - 1)
{
ll mid1 = l + (r - l) / 3;
ll mid2 = r - (r - l) / 3;
if (mid1 == l && mid2 == r)break;
if (f(mid1) < f(mid2))
r = mid2;
else
l = mid1;
}
ll minn = LLONG_MAX;
for (ll i = l; i <= r; i++)
{
ll temp = f(i);
if (temp < minn)minn = temp;
}
return minn;
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> a >> b >> c;
ll temp = SanFen(0, c / b);
cout << temp << endl;
}
return 0;
}
糟糕，出错了...使用的都是标准模板，为什么还会出错呢？
有幸获取到了本题的输入数据，跑了一遍，果然发现了几个错误结果。
以1 1 267974913236856316这个数据为例展开分析吧，程序输出1035325868，标准答案1035325867。
首先看到这个数据，心就凉了半截，这个数据足够大所以很容易覆盖到非常边角的bug，又不太好找出bug。既然最小值出错了，那么找到的极值点肯定也是错的。开循环试了一下程序找到的极值点周边的数，果然正确的极值点比程序找到的极值点偏移了两万多...
确定了问题，却一直找不到bug在哪，最后不得不把极值点周围的函数图象画出来找bug......
从图像上看，极值点非常“明显”。但实际上，在范围为40000的区间内，y的值差异极小（MATLAB默认使用double类型，所以有小数点）如果不使用double类型而使用整型，函数图象在此区间几乎成一条直线。三分函数在逼近极值点的时候，进入了错误的区间，最后找到的极值点就是错误的。因为是在靠近极值点的区域进入了错误的区间，所以极值点偏移的不多，最后求出的极值误差往往也只在个位数。
而要解决这个问题，要么使用double类型的三分函数（double类型无法取模），要么我们回归原始，用一种我们很熟悉的方法去做：
2.求导
回忆一下公式：$y=\frac{c}{a+b*x}+x$
求导：$-\frac{b}{(a+b*x)^{2}}+1$
令导数为0，求出极值点$x=\sqrt{\frac{c}{b}}-\frac{a}{b}$
还要注意两个地方，一个是求出的导数可能是负数，此时只要计算x=0时的值就可以了。还有一个是整型除法的误差问题，求出极值点后还要在该点左右取几个点求极值。
完整代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;
ll f(ll x)
{
ll sum = c / (a + b * x) + x;
if (c % (a + b * x))sum++;
return sum;
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> a >> b >> c;
ll x = max(ll(sqrt(c / b) - a / b),ll(0));
ll minn = LLONG_MAX;
for (ll i = max(ll(0), x - 2); i <= (x + 2); i++)
{
ll temp = f(i);
if (temp < minn)minn = temp;
}
cout << minn << endl;
}
}
3.模拟退火算法
还没写，大概率会鸽了，但是欢迎你时常回来看看并催更。
总结
三分法适用于数据较小，极值点周围y的值差异较大的情况。求导可用于数据较大的情况，但是f(x)中如果有mod运算则在大多数情况下无法使用。
参考链接：https://blog.csdn.net/caduca/article/details/43526375
特别感谢涂涂、罗少和范总的帮助。
文章标题：对极值问题的探索 文章链接：https://intmain0.com/104/ 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处 评论和私信会在第一时间回复。如果您觉得文章对您有帮助，可以点击文章右下角【分享】一下。您的鼓励是博主的最大动力！
