刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

割圆
本题将实现一个简化版的"割圆"游戏。成功点亮所有灯时,联结第一个和最后一个灯称之为"割线"。

n盏灯环形分布,顺序编号为1到n。灯的初始状态为关闭不亮。假设n为7,则第1号灯与第2、7号灯相邻,第2号灯与第1、3号灯相邻,以此类推。

灯的点亮规则如下:

1、输入m个数,每个数为某个灯的编号,可能重复或只是部分编号;

2、m个数中的第1个数所对应的灯,默认点亮;

3、 如果输入数对应灯的左侧或右侧已被点亮,则点亮自身。否则啥也不做;

4、如果所有的灯都已被点亮,则程序结束,m个数中尚未被处理的数将不再处理;

5、输出第1次和最后一次点亮灯的编号;

6、如果m个数处理完毕尚未点亮所有灯,则输出No。
时间限制:1000
内存限制:131072
输入
第一行2个整数n,m,保证3<=n<=1000,1<=m<=10000。 第二行m个数,每个数都在1到n之间,表示输入序列。
输出
如果完成了"割圆",则输出两个整数,之间用一个空格隔开,否则输出No。
样例输入

7 10
2 3 1 7 5 6 5 4 4 2

样例输出

2 4

提示
第1个数2,直接被点亮; 第2个数3,3与已亮的2相邻,被点亮; 第3个数1,1与已亮的2相邻,被点亮; 第4个数7,7与已亮的1相邻,被点亮; 第5个数5,5与4和6相邻,但4和6都没亮,什么都不做; 第6个数6,6与已亮的7相邻,被点亮; 第7个数5,5与已亮的6相邻,被点亮; 第8个数4,4与已亮的5相邻,被点亮; 此时,所有的数都被点亮,第1个点亮的是2,最后点亮的是4。

使用微信搜索喵呜刷题,轻松应对考试!

答案:

include<bits/stdc++.h>

using namespace std;

int main()

{

int n,m,t,a[10001];bool light[100]={0};

cin>>n>>m;// 7 10

for(int i=1;i<=m;i++)

{

cin>>a[i];

}

light[a[1]]=1;//第一个数的灯泡 a[1]=2

for(int i=2;i<=m;i++)

{

t=1;//假设 t=1

if(a[i]==n)//尾巴 环形分布最后一盏灯相邻的左右两边较为特殊

{

if(light[a[i]-1]==1 || light[1]==1) light[a[i]]=1;//自身亮

}

if(light[a[i]-1]==1 || light[a[i]+1]==1) light[a[i]]=1;//自身亮

for(int j=1;j<=n;j++)

{

if(light[j]==0)

{

t=0; //t赋值为0 代表当前环形内有灯未点亮

}

}

if(t==1)//t为1 代表当前环形内所有灯均点亮

{

cout<<a[1]<<" "<<a[i];return 0;

}

}

for(int i=1;i<=n;i++)

{

if(light[i]==0) //尚未点亮所有灯

{

cout<<“No”;return 0;

}

}

return 0;

}

解析:

【喵呜刷题小喵解析】:首先,我们定义了一个布尔数组`light`,用于记录每个灯是否被点亮。初始时,所有灯都未点亮,所以数组中的元素都设为0。然后,我们读取输入的灯的数量`n`和需要处理的数量`m`。接着,我们读取输入的`m`个数,并将它们存储在数组`a`中。然后,我们将第一个数对应的灯点亮,即`light[a[1]]=1`。对于接下来的每一个数,我们检查其左右两边的灯是否被点亮。如果其中一个被点亮,则点亮该灯。然后,我们检查是否所有的灯都已经被点亮。如果是,我们输出第一个和最后一个被点亮的灯的编号,并结束程序。如果所有的数都被处理完毕,但所有的灯都没有被点亮,那么输出"No"。需要注意的是,对于环形分布的最后一个灯,其相邻的灯是第一个灯,因此我们需要特殊处理。此外,在检查所有灯是否都被点亮时,我们使用了一个循环来遍历所有的灯,并检查是否有未被点亮的灯。如果有,则跳出循环。如果没有,说明所有的灯都已经被点亮,我们输出第一个和最后一个被点亮的灯的编号。最后,如果所有的数都被处理完毕,但所有的灯都没有被点亮,那么输出"No"。
创作类型:
原创

本文链接:割圆 本题将实现一个简化版的"割圆"游戏。成功点亮所有灯时,联结第一个和最后一个灯称之为"割线"。

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share