A39813. 割圆
填空题
较易
知识点
题目描述
割圆
题目描述
本题将实现一个简化版的“割圆”游戏。成功点亮所有灯时，联结第一个和最后一个灯称之为“割线”。
n盏灯环形分布，顺序编号为1到n。灯的初始状态为关闭不亮。假设n为7，则第1号灯与第2、7号灯相邻，第2号灯与第1、3号灯相邻，以此类推。
灯的点亮规则如下：
1、输入m个数，每个数为某个灯的编号，可能重复或只是部分编号；
2、m个数中的第1个数所对应的灯，默认点亮；
3、 如果输入数对应灯的左侧或右侧已被点亮，则点亮自身。否则啥也不做；
4、如果所有的灯都已被点亮，则程序结束，m个数中尚未被处理的数将不再处理；
5、输出第1次和最后一次点亮灯的编号；
6、如果m个数处理完毕尚未点亮所有灯，则输出No。
输入
第一行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 n, m;
int s, t;
int z[1005];//左边的灯
int y[1005];//右边的灯
bool b[1005];//灯是否亮着
int cnt = 0; //点亮的灯的数量
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) { //初始化左边的灯和右边的灯
z[i] = i - 1;
y[i] = i + 1;
}
z[1] = n; //1号灯的左边是n号灯
y[n] = 1; //n号灯的右边是1号灯
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
if(i == 1) { //第一个灯直接点亮
s = x;
b[x] = 1;
cnt++;
} else { //其他
if (b[z[x]] == 1 || b[y[x]] == 1) { //如果左右有灯亮
b[x] = 1; //点亮他
cnt++;
if (cnt == n) { //如果n盏灯都点亮了，输出答案
t = x;
cout << s << " " << t;
return 0;
}
}
}
}
cout << "No";
return 0;
}
上一题
下一题