poj2601

可以推公式也可以二分，我不会推公式，所以二分。这题之所以可以二分，是因为它符合一个性质，这个性质是，当你确定的a1偏大，利用a1求出的a[n+1]就偏大，大于题目中给出的a[n+1]。同理，偏小则小于。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

#define maxn 3100
#define eps 1.0e-8

int n;
double a[maxn];
double c[maxn];

double cal(double a1)
{
    a[1] = a1;
    for (int i = 2; i < n + 1; i++)
        a[i] = (a[i - 1] + c[i - 1]) * 2 - a[i - 2];
    return (a[n] + c[n]) * 2 - a[n - 1];
}

double binarysearch()
{
    double l = -1000, r = 1000;

    while (abs(r - l) > eps)
    {
        double mid = (l + r) / 2;
        if (cal(mid) > a[n + 1] + eps)
            r = mid;
        else
            l = mid;
    }
    return l;
}

int main()
{
    //freopen("t.txt", "r", stdin);
    scanf("%d", &n);
    scanf("%lf%lf", &a[0], &a[n + 1]);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &c[i]);
    printf("%.2f", binarysearch());
    return 0;
}