洛谷 P1984 [SDOI2008]烧水问题 题解【递推】【数学】【贪心】

点击量：161

   原来学信息学还可以学会烧水啊！

目录

题目描述

把总质量为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≤50000

   题目的数据范围是50000，正常操作是$ O(N^2)$，当然是不可做，只有20分。不过多推几次就可以找到规律：

   首先我们计算当有一杯水时，它没有别的有温度的水可以热传递过来，那么它就需要被加热100℃。

   现在情况是这样的： 第一杯水 100℃ 第二杯水 0℃

   接着是 第一杯水 50℃ 第二杯水 50℃ 此时不能再进行热传递，需要被加热50℃，现在分别为50℃ 100℃。

   我们为了接收到尽可能多的热传递，利用贪心，因为当$ a<c,c<b,a<b$时，$ a$与$ b$发生热传递，与$ c$与$ b$发生热传递，后者所得到的结果热量高，那么此时能量利用率也得到了提升。那么对这一杯0℃的水，与温度最小的那一杯热传递后，温度依然是最小，还可以和剩下的n-2杯热传递，以此类推，在到达不能热传递时，这杯水就能尽可能到达最高的温度，使得所需能量降低了。

   我们根据烧开第一杯水需要提供100℃，烧开第二杯水需要50℃，第三杯需要37.5℃，第四杯需要31.25℃。我们设100℃为单位1，则这个数列为{$ 1,\frac{1}{2},\frac{3}{8},\frac{5}{16} $}，注意到37.5和31.25类似8和16的分数，我们试着把它们除一下，得到以下结果：

   $ t_1=\frac{1}{1},t_2:t_1=\frac{1}{2},t_3:t_2=\frac{3}{4},t_4:t_3=\frac{5}{6}$，根据这个规律，我们找出一个通项：$ t_{i+1}:t_i=\frac{2n-1}{2n}$，在程序里做递推即可实现。

   细节问题：考试时在推导公式时，忘记将热传递后的数值更改，导致推导错误（推出了等比数列？？？），一定要反复检查啊。并且每杯水是$ \frac{1}{n}$的容量，热量的单位换算也要加上，记得×4200÷n。

Code：

#include<cstdio>
#include<cstring>

int main()
{

    double sum=100.0;
    int n;
    scanf("%d",&n);
    double lst=100.0;//t(i-1)
    for(int i=1;i<n;i++)
    {
        lst*=(1-1/(2*(i+0.0)));
        sum+=lst;
    }
    sum*=4200;
    sum/=n;//注意除以n
    printf("%.2lf\n",sum);
}