题面
直接三分
画个图感受一下,每次把小的那边的端点移过去就好了
然后三分实际上不一定要三等分的。。。
只要是区间内两个点都可以的
就是复杂度、精度问题。。。
两个点近一点的话复杂度更优
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
using namespace std; typedef double db; const db eps = 1e-6; db l, r, a[15]; int n; inline db (double x) { double ans = 0; for(int i = 0; i <= n; i++) ans = ans * x + a[i]; return ans; } int main() { scanf("%d%lf%lf", &n, &l, &r); for(int i = 0; i <= n; i++) scanf("%lf", a + i); while(r - l > eps) { db d1 = (5.5 * l + 4.5 * r) / 10, d2 = (4.5 * l + 5.5 * r) / 10; if(get(d1) > get(d2)) r = d2; else l = d1; } return printf("%.5fn", r), 0; }
|
近期评论