最近寒假闲来无事，所以开个博客记录记录自己做题时的一些想法和过程。
当时看M官方题解时感觉有点难理解和不太符合自然思路，所以来写一个我觉得比较自然的思路。
题意是有一个面积为1的地，第一次把它均分为块 1 / n（称为划分S）,分别为s1,s2,,,sn第二次再把它分成n块面积一样的块（称为划分A），分别为a1,a2,,an.现在想知道
\[\min\limits_{S, A}\{\max\limits_{p}\{\min\limits_{i=1}^{n}\{|S_i\cap A_{p_i}| \}\}\} \]题意可抽象为左部点和右部点个数均为n的二分图，每个点向另一边的所有点连边，其所有所连边权之和为1/n。题目所求答案即为一个完备匹配中最小边权的最大值。
首先想解决此题需要知道一个图论定理（证明就不证了）
hall定理：对于一个二部图G~(X,Y)，X存在一个匹配的充分必要条件为对于X的任意子集S，S的邻居个数N(S)必须大于等于S的大小|S|。
然后剩下的说白了就是抽屉原理。
考虑构造答案。假定答案为x,那么我们删掉权值<x的边，若图仍存在完备匹配，则证明可行。即我们想得到对于任何一个右部点的子图g,任意一个g的所有邻左部点个数>=|g|.
对于一个点的情形，得知只需要1/(n*n)即可，由抽屉原理易知。
对于多个点的情况，假设|g|=k,很容易发现k-1个左部点全部连满1/n的权值时所能得到的最小权值的最大值最小，故此时所剩权值为k /n - (k-1)/n =1/n,此时剩余边数为 k * n - k*(k-1) = k * ( n - k + 1),故由抽屉原理得至少有一边权值>= 1/( n * k * ( n - k +1)),对于所有k,最小权值为 k= ⌊(n+1)/2⌋
\[\frac{1}{n * ⌊(n+1)/2⌋ * ⌊(n+2)/2⌋} \]此时即为答案。
纯数学题，代码就非常简单了
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
double ans=1.0/(n*((n+1)/2)*((n+2)/2));
printf("%.9lf",ans);
}