提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  .Net

当前栏目

攻击火星

2023-02-18 16:35:28 时间

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

火星的地图是一个 n 个点的无向图（无重边无自环）。这伙外星人将按照如下方法入侵，先攻击度为 0 的点，然后是度为 1 的点，依此类推直到度为 n−1 的点。

被攻击的点会被删除，与之相连的点的度数都会 −1，且外星人攻击度为某个数的点时是同时攻击的。

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

输入格式

一个整数 n (1≤n≤50000)，表示顶点个数。

输出格式

一个数，表示最多能有多少个顶点不被删除。

样例解释

构造的图为：1⇔2⇔3，

第一轮攻击为度数为 0    的点，没有目标；

第二轮攻击度数为 0  的点，顶点 1,3 被删除；

第三轮攻击度数为2   的点，没有目标；

………… 后面都没有目标。

最后剩下一个顶点 2。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

3

样例输出

1

 

证明：

 

 

 

代码

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    if (n==1)
        cout<<0<<endl;
    else if(n==2)
        cout<<1<<endl;
    else
        cout<<n-2<<endl;        
}

 

相关文章