202 1ICPC 上海 M Harmony in Harmony 构造

题意有点绕，大概意思就是，现在你要将2个完全一样的区域都分成n份，且这n份的面积也都相同，我们将每一份区域定一个id(理解为1-n的排列)，问怎么分使得这俩个区域，相同id的子区域相交之后的共有的面积，n个共有面积的最小值能取到多少。

题解：我们将题意转化一下，把这俩次划分看成一张二分图，在所有可能的排列中，那么第一次划分的第$ii$号点和第二次划分的所有可能出现$ii$的$nn$个位置的面积并之和就是1/n,即它自己面积本身。即这是一个满二分图，其中每一个节点，其所连边的权值和为$1\mathrm{/}n1/n$ 那么现在我们就将题意转化成了要求寻找⼀个尽可能⼤的$ansans$，使得在任何满⾜上述条件的⼆分图下，都能够找到⼆分图的完美匹配，使得匹配边的权值都不低于$ansans$

容易想到一定存在一个$ans=\frac{1}{n^2}ans=\backslash frac\{1\}\{n^2\}$的构造，但这显然不是最优解。官方题解给了一个很巧妙的思路，我们现在取前$tt$个白点,将其和前$t-1t-1$个黑点连边，每条边的权值都为$\frac{1}{nt}\backslash frac\{1\}\{nt\}$,那么显然这$t-1t-1$个黑点的权值已经连完了，而每个白点还剩下$\frac{1}{nt}\backslash frac\{1\}\{nt\}$的权值可以连给其它黑点，我们将$\frac{1}{nt}\backslash frac\{1\}\{nt\}$平均分给剩下的$n-t+1n-t+1$个黑点，然后这些黑点再和剩下的$n-tn-t$个白点连边，可以发现在所有连边中，最小的权值便为$\frac{1}{nt(n-t+1)}\backslash frac\{1\}\{nt(n-t+1)\}$

现在尝试证明$nt(n-t+1)>=n^{2}nt(n-t+1)>=n^2$

现在$tt$是未知数，进行二次函数展开化简后即证明$-n{t}^2+(n^2+n)t-n^2>=0-nt^2+(n^2+n)t-n^2>=0$

进行求根后可得$x1=1,x2=2nx1=1,x2=2n$,又因为这个函数开口向下，且$t\in [1,n]t\backslash in[1,n]$，所以证明完毕。

因此对于$nt(n-t+1)nt(n-t+1)$这个函数，所能取到的最大值就是当$t=\frac{n+1}{2}t=\backslash frac\{n+1\}\{2\}$（对称轴）的时候，因为$tt$属于整数域，所以当$tt$为偶数的时候，最大值取不到，要取其左右俩边。综上，该函数的最大值就是$n\lfloor \frac{n+1}{2}\rfloor \lfloor \frac{n+2}{2}\rfloor n\; \backslash lfloor\; \backslash frac\{n+1\}\{2\}\; \backslash rfloor\; \backslash lfloor\; \backslash frac\{n+2\}\{2\}\; \backslash rfloor$

对应答案的最小值就是，$\frac{1}{n\lfloor \frac{n+1}{2}\rfloor \lfloor \frac{n+2}{2}\rfloor }\backslash frac\{1\}\{n\; \backslash lfloor\; \backslash frac\{n+1\}\{2\}\; \backslash rfloor\; \backslash lfloor\; \backslash frac\{n+2\}\{2\}\; \backslash rfloor\}$，直接输出即可

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define set9 fixed<<setprecision(9)
#define set12 fixed<<setprecision(12)
#define set2 fixed<<setprecision(2)
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define db double
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--) 
using namespace std;
const int maxn=2e5+5;
const ll mod=1e9+7;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll Inverse(ll x) { return qpow(x,mod-2);}


int main()
{
    int n;
    cin>>n;
    int t1=(n+1)/2,t2=(n+2)/2;
    double val=n*t1*t2;
    double ans=(1.000000)/val;
    cout<<set9<<ans<<endl;                        
}