首页 > 代码库 > UVA1555-- Garland(推导+二分)
UVA1555-- Garland(推导+二分)
题目链接
题意:有n个灯,给定第一盏灯A的高度,接下去每盏灯的高度按照公式计算,求使所有灯都不会落在地上(允许碰触)的B的最低高度。
思路:根据题目所给公式Hi=(Hj+1+Hj?1)/2?1,转化为Hi+1=2?Hi?Hi?1+2
当我们已知H1时,我们就可以二分枚举H2,求出符合题意的最小的B
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const double MAXN = 2000; const int N = 1000; int n; double A, B, H[N]; int judge(double mid) { H[2] = mid; for (int i = 3; i <= n; i++) { H[i] = 2 * H[i - 1] - H[i - 2] + 2; if (H[i] < 0) return false; } B = H[n]; return true; } int main() { while (scanf("%d %lf", &n, &A) != EOF) { memset(H, 0, sizeof(H)); double L = 0, R = MAXN, mid; H[1] = A; while (R - L > 1e-8) { mid = (L + R) / 2; if (judge(mid)) R = mid; else L = mid; } printf("%.2lf\n", B); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。