首页 > 代码库 > uva 1555 Garland
uva 1555 Garland
题意:有n个灯笼,第一个的高度是A,最后一个是B,灯笼的关系给出,并要求每个灯笼的高度是非负数的,求最低的B
思路:推出公式:H[i]=2*H[i-1]+2-H[i-2],然后枚举H[2],在知道H[1]的情况下就能求出所有的高度,然后判断是否都是非负数
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int MAXN = 1500; int n; double A, B, H[MAXN]; int check(double cnt) { H[1] = cnt; for (int i = 2; i < n; i++) { H[i] = 2*H[i-1] + 2 - H[i-2]; if (H[i] < 0) return 0; } B = H[n-1]; return true; } int main() { while (scanf("%d%lf", &n, &A) != EOF) { H[0] = A; double l = -1, r = MAXN; while (r-l > 1e-6) { double mid = (l+r)/2; if (check(mid)) r = mid; else l = mid; } printf("%.2lf\n", B); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。