题解 CF1293B 【JOE is on TV!】
呵呵侠
2020-04-10 18:25:20
我们来分析一下:
$\text{n} = 2$ 时,答案显然等于$\dfrac{3}{2}$
$\text{n} = 3$ 时,答案有三种情况:
1. $\dfrac{1}{3} + \dfrac{1}{2} + \dfrac{1}{1} = \dfrac{11}{6}$
2. $\dfrac{2}{3} + \dfrac{1}{1} = \dfrac{5}{3} = \dfrac{10}{6}$
3. $\dfrac{3}{3} = \dfrac{6}{6}$
很明显,第一种选择最佳。
$\text{n} = 4$ 时,答案有六种情况:
1. $\dfrac{1}{4} + \dfrac{1}{3} + \dfrac{1}{2} + \dfrac{1}{1} = \dfrac{25}{12}$
2. $\dfrac{1}{4} + \dfrac{2}{3} + \dfrac{1}{1} = \dfrac{23}{12}$
3. $\dfrac{1}{4} + \dfrac{3}{3} = \dfrac{5}{4} = \dfrac{15}{12}$
2. $\dfrac{2}{4} + \dfrac{1}{2} + \dfrac{1}{1} = 2 = \dfrac{24}{12}$
3. $\dfrac{2}{4} + \dfrac{1}{1} = \dfrac{3}{2} = \dfrac{18}{12}$
4. $\dfrac{3}{4} + \dfrac{1}{1} = \dfrac{7}{4} = \dfrac{21}{12}$
很显然,最佳情况还是第一种。
通过观察我们发现最佳情况就是:
$$\dfrac{1}{n} + \dfrac{1}{n - 1} + \dfrac{1}{n - 2} + …… + \dfrac{1}{2} + \dfrac{1}{1}$$
也就是:
$$\sum\limits_{i=1}^n \dfrac{1}{i}$$
那么就可以直接上手代码了:
```cpp
#include <cstdio>
using namespace std;
int main()
{
int a;
double ans = 0;
scanf("%d", &a); //其实我是想用cin的……
for(int i = 1; i <= a; i = i + 1)
ans += 1.0 / i;
printf("%f", ans); //不得不说这样写比cout要方便不少
return 0;
}
//本人其实平时用的都是iostream头文件,所以printf貌似只能输出7位小数,但是无伤大雅,因为CodeForce有Special Judge,所以不会有什么问题
```