P14081 炸弹游戏

P14081 「CZOI-R7」炸弹游戏 - 洛谷

标签：贪心

题目大意

给定一个整数$m$，你需要构造一个$n$个点的图，并且满足：

• 图包含$n$个点$m$条无向边；
• 没有重边和自环；
• 在这个图中尽可能标记多的点（原题称为炸弹），点数小于$m$，这些点满足一条边最多只有一端被标记。

你需要求出$n$的范围。

题解

对于这道题我们分两个方面分类讨论。（最大值，最小值）

1.最小值

对于最小值我们只需要满足没有重边和自环与至少m条边，即求m条边的最少不重边自环图点数。

那么我们又知道，对于一个$n$个点的无向图来说，最多有$\frac{(n-1)n}{2}$条边，那么我们即求： $$ \frac{(n-1)n}{2} \ge m $$ 然后使用初中数学知识化简得： $$ n^{2}-n-2m\ge0 $$ 最后解得： $$ n\le\frac{1- \sqrt{1+8m}}{2} \text{ 或 } n\ge\frac{1+ \sqrt{1+8m}}{2} $$ 显然节点数不可能为负数，第一项舍去。 $$ n\ge\frac{1+ \sqrt{1+8m}}{2} $$ 我们用程序求出以上不等式$n$的最小整数即为第一个答案。

2.最大值

最大值我们继续分类讨论：

1. $m\in[1,2]$：

这两种种情况无解。

1. $m=3$:

如图这种情况

.......