题目概述

在一个荒岛上，有若干人需要通过一条唯一的道路逃往两端的港口。每个人可以选择向左或向右逃生，逃生方向由输入中的正负数表示（正数表示向右，负数表示向左）。每个人的绝对值表示其战斗力。所有人移动速度相同，当两人相向而行时，会发生决斗：

• 战斗规则：
  • 战斗力较强者胜出：战斗力较强的人存活，并且其战斗力减少与对方相同的值。
  • 战斗力相同：两人同归于尽。

需要计算最终能够成功逃生的人数。如果输入中包含0，输出-1；如果没有人能够逃生，输出0。

思路

用两个栈分别模拟向右逃生的人和向左逃生的人。

具体步骤

1. 输入验证：

   • 检查输入中是否存在0，如果有，输出-1。
   • 如果输入为空，输出-1。

2. 模拟决斗过程：

   • 使用栈（Stack）来模拟向右逃生的人。
   • 遍历每个人：
     • 如果当前人向右逃生（正数），将其战斗力压入栈中。
     • 如果当前人向左逃生（负数），则与栈顶的向右逃生者进行决斗：
       • 若栈顶战斗力大于当前人，栈顶战斗力减少当前人的战斗力，当前人被消灭。
       • 若栈顶战斗力等于当前人，双方同时被消灭。
       • 若栈顶战斗力小于当前人，栈顶被消灭，当前人的战斗力减少栈顶的战斗力，继续与下一个栈顶战斗。
     • 如果当前人战斗力在与所有向右逃生者决斗后仍有剩余，则其成功逃生。

3. 统计逃生人数：

   • 栈中剩余的向右逃生者全部成功逃生。
   • 成功逃生的向左逃生者也已在决斗过程中被记录。
   • 总逃生人数为栈中向右逃生者的数量加上成功逃生的向左逃生者的数量。

cpp

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    vector<int> people;
    int num;

    while (cin >> num) {
        if (num == 0) { // 检查输入是否为0
            cout << -1 << endl;
            return 0;
        }
        people.push_back(num);
        if (cin.peek() == '\n') break;  // 读取到换行结束
    }
    
    // 检查是否输入为空
    if (people.empty()) {
        cout << -1 << endl;
        return 0;
    }

    stack<int> left;   // 向左逃生的人的战斗力栈
    stack<int> right;  // 向右逃生的人的战斗力栈

    for (int i = 0; i < people.size(); i++) {
        if (people[i] > 0) { // 向右逃生
            right.push(people[i]);
        } else { // 向左逃生
            int power = -people[i]; // 取绝对值
            while (!right.empty() && power > 0) {
                if (right.top() > power) {
                    right.top() -= power; // 向右的人继续生存
                    power = 0; // 向左的人已死
                } else if (right.top() < power) {
                    power -= right.top(); // 向右的人已死
                    right.pop();
                } else {
                    right.pop(); // 两者都死
                    power = 0; // 向左的人已死
                }
            }
            // 如果向左的人还有战斗力，说明他成功逃生
            if (power > 0) left.push(-power);
        }
    }

    // 所有向右逃生的人都成功逃生
    int totalEscapees = left.size() + right.size();
    cout << totalEscapees << endl;

    return 0;
}

python

def escape_people(people):
    left = []   # 向左逃生的人的战斗力栈
    right = []  # 向右逃生的人的战斗力栈

    for person in people:
        if person > 0:  # 向右逃生
            right.append(person)
        else:  # 向左逃生
            power = -person  # 取绝对值
            while right and power > 0:
                if right[-1] > power:
                    right[-1] -= power  # 向右的人继续生存
                    power = 0
                elif right[-1] < power:
                    power -= right.pop()  # 向右的人已死
                else:
                    right.pop()  # 两者都死
                    power = 0
            # 如果向左的人还有战斗力，说明他成功逃生
            if power > 0:
                left.append(-power)

    # 所有向右逃生的人都成功逃生
    total_escapees = len(left) + len(right)
    return total_escapees

# 输入处理
try:
    people_input = list(map(int, input().split()))
    if 0 in people_input:  # 检查输入是否包含0
        print(-1)
    else:
        print(escape_people(people_input))
except Exception as e:
    print(-1)

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static int escapePeople(int[] people) {
        List<Integer> left = new ArrayList<>();  // 向左逃生的人的战斗力栈
        List<Integer> right = new ArrayList<>(); // 向右逃生的人的战斗力栈

        for (int person : people) {
            if (person > 0) {  // 向右逃生
                right.add(person);
            } else {  // 向左逃生
                int power = -person;  // 取绝对值
                while (!right.isEmpty() && power > 0) {
                    if (right.get(right.size() - 1) > power) {
                        right.set(right.size() - 1, right.get(right.size() - 1) - power);  // 向右的人继续生存
                        power = 0;
                    } else if (right.get(right.size() - 1) < power) {
                        power -= right.remove(right.size() - 1);  // 向右的人已死
                    } else {
                        right.remove(right.size() - 1);  // 两者都死
                        power = 0;
                    }
                }
                // 如果向左的人还有战斗力，说明他成功逃生
                if (power > 0) {
                    left.add(-power);
                }
            }
        }

        // 所有向右逃生的人都成功逃生
        int totalEscapees = left.size() + right.size();
        return totalEscapees;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        try {
            String input = scanner.nextLine();
            String[] parts = input.split(" ");
            int[] people = new int[parts.length];

            for (int i = 0; i < parts.length; i++) {
                people[i] = Integer.parseInt(parts[i]);
            }

            for (int person : people) {
                if (person == 0) {  // 检查输入是否包含0
                    System.out.println(-1);
                    return;
                }
            }

            System.out.println(escapePeople(people));
        } catch (Exception e) {
            System.out.println(-1);
        } finally {
            scanner.close();
        }
    }
}

题目描述

一个荒岛上有若干人，岛上只有一条路通往岛屿两端的港口，大家需要逃往两端的港口才可逃生。

假定每个人移动的速度一样，且只可选择向左或向右逃生。

若两个人相遇，则进行决斗，战斗力强的能够活下来，并损失掉与对方相同的战斗力；若战斗力相同，则两人同归于尽。

输入描述

给定一行非 $0$ 整数数组，元素个数不超过 $30000$ ；

正负表示逃生方向（正表示向右逃生，负表示向左逃生），绝对值表示战斗力，越左边的数字表示里左边港口越近，逃生方向相同的人永远不会发生决斗。

输出描述

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

样例1

输入

5 10 8 -8 -5

输出

2

说明

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