Local Maxima是什么意思?
发布网友
发布时间：2023-09-17 15:27
共1个回答
热心网友
时间：2024-12-15 05:33
源文件：LocalMaxima.*
输入文件：LocalMaxima.in
输出文件：LocalMaxima.out
时限：1S
问题描述：
给出一个排列，如果其中一个数比它前面的数都大，则称为“Local Maxima”。现在问在一个随机给出的排列中，期望有多少个数为“Local Maxima”。
输入：
一个正整数n，表示排列为1..n的一个排列。
输出：
一个随机1..n的排列，会有多少个数为“Local Maxima”。答案四舍五入保留8位小数。
样例：
LocalMaxima.in
2
LocalMaxima.out
1.50000000
样例解释：
1，2排列一共有两种：1，2；2，1。前者两个数都为“Local Maxima”，后者仅有第一个数2为“Local Maxima”。
数据范围：
对30%的数据，n≤10。
对80%的数据，n≤1,000,000。
对100%的数据，n≤231-1。
【分析】就是这个ans:=ans+1/i
最后20分还要靠欧拉常数，而且只有在趋近无穷大的时候用。
【代码】
var
k,i:longint;
ans:extended;
begin
assign(input,'LocalMaxima.in');
reset(input);
assign(output,'LocalMaxima.out');
rewrite(output);
readln(k);
ans:=0;
if k<=10000000 then
for i:=1 to k do ans:=ans+1/i
else ans:=ln(k)+0.57721566490153286060651209;
writeln(ans:0:8);
close(input);
close(output);
end.
