算法题，单向队列每次从首尾不放回抓取物品

Question

题目如图。给定编程语言。
狗爷和小猪正在进行摸鱼游戏。池塘中游动着n条鱼，它们排成了一条直线队列，其中有m条锦鲤,每条锦鲤的具体位置已知。狗爷和小猪将轮流进行操作，每一轮中，每人都必须选择并摸走队列开头或者结尾的一条鱼，这个过程会一直持续，直到队列中仅剩下一条鱼。这时，如果唯一剩下的这条鱼是一条锦鲤，那么狗爷将获得胜利，否则邪恶的小猪将夺走锦鲤。每次游戏中，小猪将进行首次操作，可以肯定的是，小猪和狗爷俩人都非常聪明，他们总会选择对自己最有利的策略进行游戏。请判定狗爷能否取得游戏胜利。如果狗爷可以赢得胜利，输出Goldye。否则，输出Xiaozhu Ha ha ha。输入格式
第一行输入两个正整数n.m,分别代表鱼的总数和锦鲤的数量。
第二行输入m个整数，代表每条锦鲤在队列中的位置。位置编号从1到n。输出格式
输出一行字符串。如果狗爷可以赢得胜利，输出Goldye。否则，输出Xiaozhu Ha ha ha.数据范围
1≤10^5

Answer 1

本答案参考 多次询问 ChatGPT-3.5 后选择的最佳回答，若是满意，还请采纳，谢谢

这个题目的意思是让你模拟狗爷和小猪在一个队列中摸鱼的游戏。关键在于，两人会轮流操作，每次只能从队列的首尾选择一条鱼，如果最后剩下的鱼是锦鲤，狗爷赢，否则小猪赢。两人都会选择最优策略。

解题思路

• 小猪先手，狗爷后手。
• 你需要判断在小猪和狗爷都采取最优策略的情况下，最后是否能让狗爷取得胜利。
• 重点在于分析两人如何通过首尾选择影响队列的剩余锦鲤。

实现步骤

1. 首先，输入 n 和 m，分别是鱼的总数和锦鲤的数量。
2. 然后，记录所有锦鲤的位置。
3. 判断在最优策略下，最后剩下的鱼是不是锦鲤。

C++代码框架

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> koi(m);  // 锦鲤的位置
    for (int i = 0; i < m; ++i) {
        cin >> koi[i];
    }

    // 计算锦鲤的最左和最右位置
    int left = *min_element(koi.begin(), koi.end());
    int right = *max_element(koi.begin(), koi.end());

    // 小猪和狗爷都采取最优策略
    if ((n - m) % 2 == 1) {
        // 如果总的非锦鲤鱼数量是奇数，小猪能操控局面
        cout << "Xiaozhu Hahaha" << endl;
    } else {
        // 否则，狗爷可以赢
        cout << "Goldye" << endl;
    }

    return 0;
}

说明

• n - m 是总的非锦鲤鱼的数量，如果它是奇数，那么小猪会有优势，因为她是先手。
• 如果非锦鲤鱼数量是偶数，狗爷就可以获胜。

你可以使用这个思路并进一步优化程序处理大规模的数据。