POJ 1759 Garland 题解 《挑战程序设计竞赛》

POJ 1759 Garland

花环：N个灯泡离地H_i，满足H1 = A ，Hi = (H_i-1 + H_i+1)/2 – 1，HN = B ，求最小B。

3.1不光是查找值！“二分搜索”

其他

关键是选取什么值作为mid，已知A，如果知道第二个高度h2的话，就可以推出h3，然后又可以利用h2和h3推出h4。所以h2才是关键，设mid为h2，二分条件为mid可以使得所有灯泡高度大于零。

从严密性的角度讲，h2的大小是跟B正相关的，满足二分单调性的要求。

#include <iostream>
#include <iomanip>
using namespace std;
#define MAX_A 1000
#define MAX_N 1000 + 16
int N;
double A, B, H[MAX_N];

bool C(const double& mid)
{
	H[1] = mid;
	for (int i = 2; i < N; ++i)
	{
		H[i] = 2 * H[i - 1] + 2 - H[i - 2];
		if (H[i] < 0)
		{
			return false;
		}
	}
	B = H[N - 1];
	return true;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> N >> A;
	H[0] = A;
	double lb = -1, ub = MAX_A + 16;
	for (int i = 0; i < 100; ++i)
	{
		double mid = (ub + lb) / 2;
		if (C(mid))
		{
			ub = mid;
		}
		else
		{
			lb = mid;
		}
	}
	cout << fixed << setprecision(2) << B << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

这个太神奇了，0毫秒。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1759 Garland 题解 《挑战程序设计竞赛》