題意:有n個燈笼,第一個的高度是A,最後一個是B,燈笼的關系給出,並要求每個燈笼的高度是非負數的,求最低的B
思路:推出公式:H[i]=2*H[i-1]+2-H[i-2],然後枚舉H[2],在知道H[1]的情況下就能求出所有的高度,然後判斷是否都是非負數
#include#include #include #include 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; }