关于#c++#的问题，如何解决？

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

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。

参考GPT和自己的思路：

这个问题可以使用C++语言来解决。首先，我们需要定义一个bool类型的数组来存储每个灯的状态，即是否点亮。然后，对于输入的m个数，我们可以通过遍历数组来判断每一个数的左右是否已经点亮，如果是则点亮当前灯，否则不做处理。循环结束后，如果所有的灯都已经点亮，则输出第一个和最后一个点亮的灯的编号，否则输出No。

下面是可能的一种代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m;
bool light[MAXN];

int main() {
    memset(light, false, sizeof(light)); // 初始化为所有灯都未点亮

    cin >> n >> m;
    int first = 0, last = 0; // 记录第一盏点亮的灯和最后一盏点亮的灯的编号

    for (int i = 0; i < m; i++) {
        int num;
        cin >> num;

        if (!light[num]) { // 如果当前灯未点亮
            if (i == 0) { // 如果是第一个数，则将当前灯点亮
                light[num] = true;
                first = num;
                last = num;
            } else { // 如果不是第一个数
                int left = (num - 1 + n) % n; // 计算当前灯的左侧灯的编号
                int right = (num + 1) % n; // 计算当前灯的右侧灯的编号

                if (light[left] || light[right]) { // 如果左侧或右侧已经点亮
                    light[num] = true;
                    last = num;
                } // 否则啥也不做
            }
        }

        if (i == m - 1 && count(light + 1, light + n + 1, true) != n) { // 如果所有的数都处理完了但是不是所有灯都点亮了 
            cout << "No" << endl;
            return 0;
        }
    }

    cout << first << " " << last << endl;
    return 0;
}

该回答引用GPTᴼᴾᴱᴺᴬᴵ
以下是该题的 C++ 代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1010;
int n, m, vis[MAXN];

int main() {
    cin >> n >> m;
    memset(vis, 0, sizeof(vis));
    int pre, cur;
    cin >> pre;
    vis[pre] = 1;
    for (int i = 2; i <= m; i++) {
        cin >> cur;
        if (vis[cur]) continue;
        if (cur == pre + 1 || cur == pre - 1 || cur == pre + n - 1 || cur == pre - n + 1) {
            vis[cur] = 1;
        }
        pre = cur;
    }
    int cnt = 0, first, last;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            cnt++;
            if (cnt == 1) first = i;
            if (cnt == n) last = i;
        }
    }
    if (cnt == n) {
        cout << first << " " << last << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

解释如下：

首先，我们定义一个数组 vis，表示每个灯的状态，初始时所有灯都是关闭的，即 vis[i] = 0。

我们用 pre 表示上一个被点亮的灯的编号，cur 表示当前输入的灯的编号。由于灯是环形分布的，因此我们可以通过判断 cur 和 pre 的关系来确定是否需要点亮当前的灯。

如果 cur 是 pre 的左侧或右侧相邻的灯，则点亮 cur，即 vis[cur] = 1。特别地，如果 cur 和 pre 相邻但跨越了首尾两端，即 cur = pre + n - 1 或 cur = pre - n + 1，也视为相邻。

最后，我们遍历一遍 vis 数组，统计被点亮的灯的个数 cnt。如果 cnt = n，说明所有的灯都被点亮了，输出第一个被点亮的灯的编号和最后一个被点亮的灯的编号；否则，输出 No。

需要注意的是，本题中给定的 m 个数可能重复或只是部分编号，因此我们需要对输入数据进行去重处理，即如果一个灯已经被点亮了，则直接跳过。