蒜头君在玩一个战争模拟游戏，他有高度为 1,2,3,\ldots ,n1,2,3,…,n 的炮台各一个，他需要把这 nn个炮台从左往右排成一行，并且炮口都朝向右边。
在这个游戏中，所有炮台发射的炮弹会摧毁前方所有高度比自己低的炮台。每当蒜头君把 nn个炮台排成一行后，可能会有一些炮台被摧毁。举个例子：当前有 55 个炮台，从左到右高度分别为 2,1,3,5,42,1,3,5,4，往右发射炮弹后，高度为 44 的炮台被高度为 55 的摧毁，高度为 11 的炮台被高度为 22 的炮台摧毁，最后只会剩下 2,3,52,3,5 这三个炮台。
现在蒜头君想知道，如果随机地摆放这 nn 个炮台，最后剩下炮台个数的期望是多少？比如 n=2n=2 时，有两种摆放方式，高度序列分别为 1,21,2 和 2,12,1，前者最后剩下 22 个炮台，后者最后剩下一个炮台，因此期望为 {(2+1)\over 2}=1.50002(2+1)=1.5000。
请你求出 n=2019n=2019 时剩下炮台个数的期望，保留四位小数。
样例输入复制
无
样例输出复制
无
题解：答案是"8.1878"，看了视频讲解后才知道怎么做的。题解就是算每个炮台对答案的贡献。
最高的炮台贡献是1。第二高的炮台，只需要考虑它和最高的炮台位置关系，如果在前面，则留下否则挂掉，所以贡献是1/2，同理，第三个炮台位于前2个炮台左边或中间或右边，贡献为1/3.。。。
所以答案是1+1/2+1/3+.....+1/n
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
