A2291 | 攻击火星
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
一群外星人将要攻击火星。
火星的地图是一个 $n$ 个点的无向图。这伙外星人将按照如下方法入侵，先攻击度为 $0$ 的点（相当于从图中删除掉它），然后是度为 $1$ 的点，依此类推直到度为 $n-1$ 的点。
所有的点度统计是动态统计的。（一个点删掉后，与之相连的点的点度都会 $-1$）。外星人攻击度为某个数的点时是同时攻击的。
你需要设计这个图的边的方案来使得未被攻击的点最多。注意：你设计的图**不允许自环及重边**。
火星的地图是一个 $n$ 个点的无向图。这伙外星人将按照如下方法入侵，先攻击度为 $0$ 的点（相当于从图中删除掉它），然后是度为 $1$ 的点，依此类推直到度为 $n-1$ 的点。
所有的点度统计是动态统计的。（一个点删掉后，与之相连的点的点度都会 $-1$）。外星人攻击度为某个数的点时是同时攻击的。
你需要设计这个图的边的方案来使得未被攻击的点最多。注意：你设计的图**不允许自环及重边**。
输入格式
输入文件包含一行一个整数 $n$。
输出格式
一行一个整数，表示最多的最后未被攻击的点。
输入输出样例
输入 #1
3
输出 #1
1
【样例解释】
一种可能的方案是 $1\leftrightarrow 2\leftrightarrow 3$，这样首先删掉度为 $1$ 的点 $1$ 和点 $3$，此时点 $2$ 度数为 $0$，不会被删去。
【数据范围】
- 对于 $20\%$ 的数据 $1\le n\le 10$；
- 对于 $100\%$ 的数据 $1\le n\le 5\times 10^4$。
一种可能的方案是 $1\leftrightarrow 2\leftrightarrow 3$，这样首先删掉度为 $1$ 的点 $1$ 和点 $3$，此时点 $2$ 度数为 $0$，不会被删去。
【数据范围】
- 对于 $20\%$ 的数据 $1\le n\le 10$；
- 对于 $100\%$ 的数据 $1\le n\le 5\times 10^4$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？