来自"NOCOW"

---

Solution From Xcheng：

由已知有：

   H(i)=2H(i-1)+2-H(i-2)

法一：

   设H(i)=P(i)*H(1)+Q(i)*H(2)+R(i).....*

   将i<-i-1代回原式，得

   P(i)=2*P(i-1)-P(i-2)

   Q(i)=2*Q(i-1)-Q(i-2)

   R(i)=2*R(i-1)+2-R(i-2)

   初始值：P(1)=1 Q(2)=1

   求PQR的通项，有 P(i)=2-i;Q(i)=i-1;R(i)=(i-1)*(i-2)

   题目求的是使 每一个H(i)=P(i)*H(1)+Q(i)*H(2)+R(i)>=0 的最小值 H(n)
   
   显然，H(n)的值仅随H(2)的变化而变化（因为H(1)已知，R,P,Q已知）

   又因为Q(i)>=0，所以要求H(2)的最小值。
   
   于是得出算法：对于i<---3 to n  计算更新H(2)的最小值，最后求出H(n)

法二：

   直接二分枚举H(2),求出每一个H(i)，判断是否可行。

---

由图（和题目背景）可以看出，这题可以二分答案。但是不是二分B点，也不是二分最低点，而是二分H(2)

program cao;
var
  f,g,h,j,i,k,l,n,m,p,q:longint;
  top,bot,mid,a,b,c,d,e:extended;
 
function can(x:extended):boolean;
begin
  a:=e;
  b:=x;
  for i:=3 to n do
  begin
    c:=2*b+2-a;
    a:=b;
    b:=c;
    if c<0 then exit(false);
  end;
  exit(true);
end;
 
begin
  read(n,e);
  top:=e;
  bot:=0;
  while top-bot>1e-5 do
  begin
    mid:=(top+bot)/2;
    if can(mid) then top:=mid
    else bot:=mid;
  end;
  a:=e;
  b:=mid;
  for i:=3 to n do
  begin
    c:=2*b+2-a;
    a:=b;
    b:=c;
  end;
  writeln(c+1e-5:0:2);
end.

http://www.withflying.com/?p=128

http://www.withflying.com

---

我给出一个O(1)的算法。

由已知可推导出：

   H(i + 1) - H(i) = H(i) - H(i - 1) + 2

令t = H(2) - H(1)，则有：

   H(k + 1) = H(1) + k * t + k * (k - 1) >= 0 (1 <= k <= n - 1)  <--- 不等式1

而

   H(n) = H(1) + t * (n - 1) + (2 + 4 + ... + 2(n - 2))

所以需要求得t的最小值。将不等式1化简可得：

   t >= -(h1 / k + k) + 1 (1 <= k <= n - 1)

我觉得到这儿之后就很清晰了。给出AC程序：（原先0.015s过的程序改了改缩进之后居然变成了0.031s……rp很重要……）

#include <stdio.h>
#include <math.h>
 
int main(void)
{
    double k, h1, ans, p = 10000000;
    int n;
    scanf("%d %lf", &n, &h1);
    ans = (n - 1) * (n - 2);
    k = ceil(sqrt(h1));
    if(k <= n - 1)
        p = h1 / k + k;
    k = floor(sqrt(h1));
    if(k <= n - 1 && p > h1 / k + k)
        p = h1 / k + k;
    if(p == 10000000)
        p = h1 / (n - 1) + n - 1;
    p = -p + 1;
    ans += p * (n - 1) + h1;
    printf("%.2lf", ans);
    return 0;
}

--Wecing 17:12 2010年5月8日 (CST)