[ARC161D] Everywhere is Sparser than Whole (Construction)

构造题，重在思路，代码不难。

考虑有一个性质，既然部分比整体更稀疏，那么需要每个点的入度都 \(>d\)，因为这样删去之后 \(\div(n-1)\) 才会减小。形式化的说，需要满足

\[记 cnt=\min(度_i(1\le i\le n))\\ d>\dfrac{nd-cnt}{n-1} \]

解得 \(cnt>d\)。

然后构造方案方案如下：

一个有 \(N\) 个顶点的简单无向图最多只能有 \(\frac{N(N-1)}{2}\) 条边，因此当 \(D > \frac{N-1}{2}\) 时，答案为 No。反之，当 \(D \leq \frac{N-1}{2}\) 时，答案为 Yes。例如，对于每个 \(i=1,2,\dots,N\) 和每个 \(k=1,2,\dots,D\)，可以连接顶点 \(i\) 和顶点 \((i+k)\)（如果 \(i+k>N\)，则连接顶点 \((i+k-N)\)），这样就可以得到一个满足条件的简单无向图。