荒岛逃生游戏

题目描述

一个荒岛上有若干人，岛上只有一条路通往岛屿两端的港口，大家需要逃往两端的港口才可逃生。假定每个人移动的速度一样，且只可选择向左或 向右逃生。若两个人相遇，则进行决斗，战斗力强的能够活下来，并损失掉与对方相同的战斗力;若战斗力相同，则两人同归于尽。

输入描述

给定一非0整数数组，元素个数不超过30000;正负表示逃生方向(正表示向右逃生，负表示向左逃生)，绝对值表示战斗力，越左边的数字表示离左边港口越近，逃生方向相同的人永远不会发生决斗。

输出描述

能够逃生的人总数,没有人逃生输出0，输入异常时输出-1。

示例1

输入：
5 10 8 -8 -5

输出：
2

说明：
第3个人和第4个人同归于尽，第2个人杀死第5个人并剩余5战斗力，第1个人没有遇到敌人。

C++

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

int main() {
    int p;
    vector<int> stk; // 用栈存储向右侧逃生中的人
    int cnt = 0; // 记录从左侧可以成功逃生的人数
    
    // 处理输入数据
    while(cin >> p) {
        if (p > 0) { // 如果是正数，表示向右逃生，加入栈
            stk.push_back(p);
        }else{ // 如果遇到负数，表示向左逃生
            while (!stk.empty() && p < 0) {
                int last = stk.back(); // 栈顶元素
                stk.pop_back(); // 弹出栈顶元素

                p += last; // 进行决斗，战斗力相加
            }

            if (p < 0) { // 左逃生成功，计数
                cnt++;
            }else if(p > 0){ // 左逃生失败
                stk.push_back(p);
            }
        }
    }

    // 输出能逃生的人的数量
    cout << cnt + stk.size() << endl;
}

解题思路

1. 栈的使用：我们可以使用栈来模拟人们的逃生过程。每当遇到一个向右逃生的人（正数），我们将其加入栈中；而当遇到一个向左逃生的人（负数）时，可能会发生决斗：
   • 如果栈中有向右逃生的人，则进行决斗，战斗力较强的一方胜利。
   • 如果战斗力相同，双方都同归于尽。
   • 如果没有向右逃生的人，则该向左逃生的人直接逃生。
2. 栈的更新：
   • 当一个人向左逃生时，首先检查栈中是否有向右逃生的人，如果有，则比较战斗力。
   • 如果向右逃生的人更强，栈中的人减少，向左逃生的人继续与栈中的人决斗。
   • 如果向左逃生的人战斗力足够强，则可以杀死栈中的人，继续决斗，直到没有人阻挡他，或者他战斗力为负（即同归于尽）。
3. 最后的结果：栈中剩余的人表示逃生成功的人数。没有遇到敌人的人直接逃生。每个人的战斗力将会影响最终的逃生结果。
4. 输入异常处理：如果输入非法（如非整数输入），则输出 -1。

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏