最值

题意

你只知道函数 \(f(x) = \sum_{i=1}^{n} |x - x_i|,(\forall i \in [1, n], x_i \in [1, m] ∩ Z)\) 和值域 \([1,m], m\leq10^7\)。 你可以询问 \(x\) 点的取值，在 \(34\) 次询问内，求 \(f(x)\) 的最小值。

三分法

假设 \(x_i\) 是排好序的，那么其实能发现这个函数是一个 凹函数。

更强的结论，答案的取值的点就是序列 \(x_i\) 的中位数，不过没有用，无法找出。

能发现这这种函数的斜率其实在单调递增，一般就是二分斜率，找到斜率为 0 的地方，也叫三分法。

一般的三分每缩小一次范围要求两个三等分点的值，那么就能在 \(2 \log_2 m\) 次询问中求出最值。

但是 \(2 \log_2 m \approx 46 \geq 34\)。

斐波那契,黄金分割

每次都要求两个三等分点的取值，下一次就重新再求另外两个，这样显得很浪费。

能否重复利用上一次询问的点呢？

设现在的区间是 \([l,r]\), \(f_0,f_1\) 分别是第一个等分点和第二个等分点，\(l\) 到 \(f_1\) 的距离是 \(\phi\), \(l\) 到 \(f_0\) 的距离是 \(1\)。

假如缩小范围 \([l',r'],l' = l, r' = f_1\), 设 \(f_0\) 是现在区间的第二个等分点，那么 第二等分点到左端点的距离 占 总长的 \(\frac{1}{\phi}\), 因此推出现在的 \([l, r]\) 长 \(\phi^2\)。

假如缩小范围 \([f_0, r]\)，由于是要较为等分，看得出来现在的区间和上面假设的区间是对称的，这时 \(f_1\) 到右端点 和 \(l\) 到 \(f_0\) 的距离相等，都为一。

• 于是就有 \(1 + \phi = \phi^2\) ，解得 \(\phi = \frac{1 + \sqrt{5}}{2}\)。

实际上就是黄金分割点。

• \(f_0\) 占总长的 \(\frac{1}{1+\phi} = \frac{3-\sqrt{5}}{2}\),

• \(f_1\) 占总长的 \(\frac{\phi}{1 + \phi} = \frac{\sqrt{5} - 1}{2}\)。

这样下一次的决策就能用到当前的算出的值。

要注意：由于取值是整数，可能有所误差，要四色五入，直接转换类型是向下取整。

代码:

在实现上避免误差可以用斐波那契数列。

#include  
using namespace std;

extern long long get(int x);

long long min(long long a, long long b) {
	return a > b ? b : a; 
}

const double eps = 1e-8;	
const double f0 = 1.0 * (3 - sqrt(5)) / 2, f1 = 1.0 * (sqrt(5) - 1) / 2;

map mp; 
long long Get(int x) {
	if (mp.find(x) != mp.end()) return mp[x]; 
	return mp[x] = get(x); 
}

long long guess(int m) {
	double l = 1, r = m;
	while (1) {
		double F0 = (r - l) * f0 + l, F1 = (r - l) * f1 + l; 
		int mid = round(F0), midd = round(F1); 
		if ((int)l == mid || (int)r == midd) {
			long long ans = 1e18;
			for (int i = l; i <= r; i ++) 
				ans = min(ans, Get(i));
			return ans;
		}
		long long val1 = Get(mid), val2 = Get(midd); 
		if (val2 > val1) r = F1;
		else l = F0; 
	}
}