【LG P1984】烧水问题

SDOI2008]烧水问题

分析

这道题是一道较难以看出来的贪心。

首先先加热第一杯水，然后通过热传递，尽量加热温度最高的，在与次高的热传递中：

为了方便起见，每杯水升 (1)℃ 需要消耗 (1 exttt{J})，假设有 (4) 杯水。

第一杯水需要消耗 (100 exttt{J}) 的能量。

第二杯水需要消耗 (50 exttt{J}) 的能量。

第三杯水需要消耗 (37.5 exttt{J}) 的能量。

第四杯水需要消耗 (31.25 exttt{J}) 的能量。

……设第 (i) 杯水花费的能量为 (large{mathrm{cost}_i})。

那么：

[mathrm{cost}_2=frac{1}{2}mathrm{cost}_1\ mathrm{cost}_3=frac{3}{4}mathrm{cost}_2\ mathrm{cost}_4=frac{5}{6}mathrm{cost}_3\ mathrm{cost}_{i+1}=mathrm{cost}_i(1-frac{1}{2i}),iinmathbb{N^+} ]

代码

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	double res,now;
	scanf("%d",&n);
	now=420000.00/n;
	for(int i=1; i<=n; i++) {
		res+=now,now*=(1-0.5/i);
	}
	printf("%.2lf",res);
	return 0;
}