放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

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

目录

POJ 1759 Garland

花环:N个灯泡离地H_i,满足H1 = A ,Hi = (Hi-1 + Hi+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毫秒。

12852033 hankcs 1759 Accepted 228K 0MS C++ 972B 2014-05-08 13:49:50

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

分享到:更多 ()

评论 3

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #3

    应该是求满足条件的最小B

    1年前 (2016-07-29)回复
  2. #2

    题目不是说要求最小的B么?

    why1年前 (2016-06-10)回复
  3. #1

    我来点个赞

    guocq2年前 (2015-07-12)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机