P1984 [SDOI2008] 烧水问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) #找规律 思维 T3
题目描述
把总质量为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
样例输入 #1
2
样例输出 #1
315000.00
提示
1≤n≤3000000
思路
给你几杯水, 求把每杯水都沸腾一次的最小加热能量。其中可以进行传导操作, 如100度的水给0度传导, 两者的温度会到达平衡态即均为50度。
显然可以贪心的考虑, 加热第一杯水后, 把它的温度传给后面的所有水, 第一杯传50, 第二杯传25…。然后加热第二杯, 接着往后传导。
不过题目条件最大有300万个杯子, 无论是时间复杂度 还是精度限制都不可能实现模拟上述思路。
没法了, 找规律吧。手算一下4杯时候, 可以发现, 第一杯加热100度, 第二杯加热50度, 第三杯加热37.5度, 第四杯加热33.75度。
而把第i杯和第i-1杯所加热的温度相比, 可以发现一个规律, 。
故可以直接根据这个推导式以 的复杂度解决。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int main()
{
int n;
cin >> n;
double now = 100.0;
double res = now;
for (int i = 2; i <= n; i++)
{
now = now * (2.0 * (i - 1) - 1) / (2.0 * (i - 1));
res += now;
}
printf("%.2lf", 4200.0 * res / double(n));
return 0;
}