P1416 攻击火星

    • 463通过
    • 922提交
  • 题目提供者 tinylic
  • 评测方式 云端评测
  • 标签 构造 模拟
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    一群外星人将要攻击火星。

    火星的地图是一个n个点的无向图。这伙外星人将按照如下方法入侵,先攻击度为0的点(相当于从图中删除掉它),然后是度为1的点,依此类推直到度为n-1的点。

    所有的点度统计是动态统计的。(一个点删掉后,与之相连的点的点度都会-1)。外星人攻击度为某个数的点时是同时攻击的。

    你需要设计这个图的边的方案来使得未被攻击的点最多。

    输入输出格式

    输入格式:

    输入文件包含一行一个整数n。

    输出格式:

    一行一个整数,表示最多的最后未被攻击的点。

    输入输出样例

    输入样例#1: 复制
    3
    输出样例#1: 复制
    1

    说明

    【样例解释】

    ①-②-③,这样首先删掉度为1的①和③,此时②度数为0,不会被删去。

    【数据范围】

    对于20%的数据1<=n<=10

    对于100%的数据1<=n<=50000

    【题目来源】

    tinylic改编

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。