这题是真的真的真的超级无聊。。。。

题目描述

把总质量为\(1kg\)的水分装在n个杯子里，每杯水的质量均为\((1/n)kg\)，初始温度均为\(0℃\)。现需要把每一杯水都烧开。我们可以对任意一杯水进行加热。把一杯水的温度升高\(t℃\)所需的能量为\((4200*t/n)J\)，其中，“\(J\)”是能量单位“焦耳”。如果一旦某杯水的温度达到\(100℃\)，那么这杯水的温度就不能再继续升高，此时我们认为这杯水已经被烧开。显然地，如果直接把水一杯一杯地烧开，所需的总能量为\((4200*100)J\)。

在烧水的过程中，我们随时可以在两杯温度不同的水之间进行热传递操作。热量只能从温度较高的那杯水传递到温度较低的那杯水。由于两杯水的质量相同，所以进行热传递操作之后，原来温度较高的那杯水所降低的温度总是等于原来温度较低的那杯水所升高的温度。

一旦两杯水的温度相同，热传递立刻停止。

为了把问题简化，我们假设：

1、没有进行加热或热传递操作时，水的温度不会变化。

2、加热时所花费的能量全部被水吸收，杯子不吸收能量。

3、热传递总是隔着杯子进行，\(n\)杯水永远不会互相混合。

4、热传递符合能量守恒，而且没有任何的热量损耗。

在这个问题里，只要求把每杯水都至少烧开一遍就可以了，而不要求最终每杯水的温度都是\(100℃\)。我们可以用如下操作把两杯水烧开：先把一杯水加热到\(100℃\)，花费能量\((4200*100/2)J\)，然后两杯水进行热传递，直到它们的温度都变成\(50℃\)为止，最后把原来没有加热到\(100℃\)的那杯水加热到\(100℃\)，花费能量\((4200*50/2)J\)，此时两杯水都被烧开过了，当前温度一杯\(100℃\)，一杯\(50℃\)，花费的总能量为\((4200*75)J\)，比直接烧开所需的\((4200*100)J\)少花费了25%的能量。

你的任务是设计一个最佳的操作方案使得\(n\)杯水都至少被烧开一遍所需的总能量最少。

输入格式

输入文件只有一个数\(n\)。

输出格式

输出\(n\)杯水都至少被烧开一遍所需的最少的总能量，单位为\(J\)，四舍五入到小数点后两位。

输入输出样例

输入 #1

2

输出 #1

315000.00

说明/提示

\(1≤n≤3000000\)

手算一算找规律。设个温度权值\(\in[0,1]\)
容易找到递推式：
\[ f[i]=f[i-1]*(2*i-3)/(2*i-2) \]
结束。

所以说这题是真的 好无聊啊……弄了个这么长的题目最后在草稿纸乱搞就得到了个鬼知道对不对的递推式……

#include<bits/stdc++.h>
using namespace std;

double f[3000005];
double a[3000005];

int main()
{
    int n;
    cin>>n;
    f[1]=1;
    double c=420000;
    for(int i=2;i<=n;i++)
        f[i]=f[i-1]*(2*i-3)/(2*i-2);
    double ans=0;
    for(int i=1;i<=n;i++)ans+=(f[i]);
    printf("%.2f",ans*c/n);
    return 0;
}

LGOJ P1984 [SDOI2008]【烧水问题】

原文：https://www.cnblogs.com/kion/p/11817009.html