hdu7297(杭电多校)-JZTXT

原题点这

思路：

求一个最大的 k，使得$f(n,k)$最大。
$f(n,k)$ 表示 n个数，k 处划分
当 k = 0 时，毫无疑问概率为 ${1} \over { n }$ 。
当 k > 0 时：
$f(n,k) $ = $\sum_{i = k+1}^{n}$ ${1} \over { n }$$\times$${k} \over { i-1 }$

$f(n,k) $ = ${k} \over { n }$ $\sum_{i = k+1}^{n}$ ${k} \over { i-1 }$

$f(n,k) $ = ${k} \over { n }$ $\sum_{i = k}^{n-1}$ ${k} \over { i }$

因为数据范围 $n <= 10000$, 所以预处理$\sum$${k} \over { i }$，然后$O(n)$暴力求解即可。

AC代码：

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define db double

using namespace std;

const int N = 1e5 + 10;
db sum[N];
int n;

db cal(int n, int k)
{
    return 1.0 * k / n * (sum[n-1] - sum[k-1]);
}

void solve()
{
    cin >> n;
    db ma = 1.0 / n;
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
    	db aa = cal(n,i);
    	if(aa > ma)
    	{
    	    ma = aa;
            ans = i;
    	}
    }
    cout << ans << '\n';
}

signed main()
{
    for(int i = 1; i < N; i ++) sum[i] += sum[i-1] + 1.0 / i;
    int T = 1;
    cin >> T;
    while(T --)
    {
        solve();
    }
    
    return 0;
}