E卷-刷题笔记合集🔗

荒岛求生

问题描述

在一个荒岛上，有若干人需要逃生。岛上只有一条路通往岛屿两端的港口，每个人都必须选择向左或向右逃生才能到达港口。假设所有人的移动速度相同，但他们的战斗力不同。

当两个人相遇时，他们会进行决斗。战斗力较强的人能够活下来，但会损失与对手相同的战斗力。如果两人战斗力相同，则两人都会死亡。逃生方向相同的人永远不会发生决斗。

输入格式

输入为一行非零整数，用空格分隔。整数的个数不超过 。

每个整数的正负表示逃生方向（正表示向右逃生，负表示向左逃生），绝对值表示战斗力。数组中越靠左的数字表示该人离左边港口越近。

输出格式

输出一个整数，表示能够成功逃生的人数。

如果没有人能够逃生，输出 。 如果输入异常，输出 。

样例输入1

5 10 8 -8 -5

样例输出1

2

样例输入2

-5 10 8 -8 5

样例输出2

3

样例输入3

5 -5

样例输出3

0

样例解释

样例 解释说明

样例1	第3个人和第4个人同归于尽，第2个人杀死第5个人并剩余5战斗力，第1个人没有遇到敌人。因此共有2人逃生成功。
样例2	第1个人和第5个人分别从左右两端逃生成功。第2个人杀死第4个人后剩余2战斗力，继续向右逃生成功。共有3人逃生成功。
样例3	两个人相遇后同归于尽，没有人能够逃生。

数据范围

• ，其中 为输入整数的个数。
• ，其中 为输入的每个整数。
• 

题解

模拟

这道题的核心在于模拟荒岛上人们的逃生过程。解题的关键 在于理解人们相遇和决斗的规则，并找到一种高效的方法来处理这些相遇和决斗。

一个巧妙的解法是使用栈结构。可以想象所有人都在向左移动，这样就可以从左到右遍历输入数组，依次处理每个人的情况。

具体步骤如下：

1. 创建一个栈来存储向右逃生的人（正数）。

2. 从左到右遍历输入数组：

   • 如果遇到正数（向右逃生的人），直接将其压入栈中。
   • 如果遇到负数（向左逃生的人），将其与栈顶的人进行比较：
     • 如果栈为空，说明这个人可以直接逃生，计数加1。
     • 如果栈不为空，比较两人的战斗力（取绝对值）：
       • 如果栈顶的人战斗力更强，更新栈顶的人的战斗力，继续处理下一个人。
       • 如果当前人战斗力更强，弹出栈顶的人，并继续与新的栈顶比较。
       • 如果战斗力相等，弹出栈顶的人，当前人也死亡，继续处理下一个人。

3. 最后，栈中剩余的人数加上成功向左逃生的人数，就是最终的答案。

这种方法的时间复杂度是 O(N)，其中 N 是输入数组的长度。因为每个人最多只会被压入和弹出栈一次，所以整体的操作次数不会超过 2N。

空间复杂度是 O(N)，最坏情况下（所有人都向右逃生）栈会存储所有的人。

对于给定的数据范围（N ≤ 30000），这个解法是高效且可行的。

参考代码

• Python

def escape_island(people):
    """
    模拟荒岛逃生过程，计算成功逃生的人数
    
    :param people: 列表，表示每个人的逃生方向和战斗力
    :return: 整数，表示成功逃生的人数
    """
    stack = []  # 用于存储向右逃生的人
    escaped = 0  # 成功逃生的人数
    
    for person in people:
        if person > 0:  # 向右逃生的人
            stack.append(person)
        else:  # 向左逃生的人
            while stack:
                if abs(stack[-1]) > abs(person):  # 栈顶的人胜利
                    stack[-1] -= abs(person)
                    break
                elif abs(stack[-1]) < abs(person):  # 当前人胜利
                    person += stack.pop()
                else:  # 两人同归于尽
                    stack.pop()
                    break
            else:  # 栈为空，说明这个人成功逃生
                escaped += 1
    
    return escaped + len(stack)  # 返回总的逃生人数

# 读取输入
try:
    people = list(map(int, input().split()))
    if not people or any(p == 0 for p in people):
        raise ValueError
    result = escape_island(people)
    print(result)
except ValueError:
    print(-1)  # 输入异常时输出-1

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 30000

// 栈结构定义
typedef struct {
    int data[MAX_N];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 压栈操作
void push(Stack* s, int value) {
    s->data[++(s->top)] = value;
}

// 出栈操作
int pop(Stack* s) {
    return s->data[(s->top)--];
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}

// 获取栈顶元素
int top(Stack* s) {
    return s->data[s->top];
}

// 模拟荒岛逃生过程
int escapeIsland(int* people, int n) {
    Stack stack;
    initStack(&stack);
    int escaped = 0;

    for (int i = 0; i < n; i++) {
        if (people[i] > 0) {  // 向右逃生的人
            push(&stack, people[i]);
        } else {  // 向左逃生的人
            while (!isEmpty(&stack)) {
                if (abs(top(&stack)) > abs(people[i])) {  // 栈顶的人胜利
                    int temp = pop(&stack);
                    push(&stack, temp + people[i]);
                    break;
                } else if (abs(top(&stack)) < abs(people[i])) {  // 当前人胜利
                    people[i] += pop(&stack);
                } else {  // 两人同归于尽
                    pop(&stack);
                    break;
                }
            }
            if (isEmpty(&stack)) {  // 栈为空，说明这个人成功逃生
                escaped++;
            }
        }
    }

    return escaped + stack.top + 1;  // 返回总的逃生人数
}

int main() {
    int people[MAX_N];
    int n = 0;
    char line[MAX_N * 12