(B卷,200分)- 荒岛求生（Java & JS & Python & C）

题目描述

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

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

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

输入描述

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

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

输出描述

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

用例

题目解析

本题可以利用栈结构解题。

解题思路如下：

我们可以假设所有数字都向左逃生，那么从左边出来的只有两种情况：

• 正数
• 负数

如果左边出来的是正数，则由于正数不能从左边逃生，而只能从右边出口逃生，因此我们不能算该正数逃生成功，并且该正数还会成为左边出来的负数的逃生阻力，因此我们将左边出来的正数缓存进栈中。

如果左边出来的是负数，则由于负数可以从左边出口逃生，因此此时，我们需要检查栈中有没有缓存的正数（阻力），如果有，则需要将左边逃出来的负数 和 栈顶的正数，进行pk（二者求和）：

假设负数逃生成功个数为negative，正数逃生成功个数为positive

• 若 pk > 0，则负数逃生失败，栈顶正数减少战斗力后重新入栈
• 若 pk < 0，则负数打败了栈顶正数，负数减少战斗力，然后继续和新的栈顶正数pk：

1. 若栈已经空了，则此负数逃生成功，我们将负数逃生成功个数negative+1
2. 若栈未空，则继续pk逻辑

• 若 pk == 0，则负数和栈顶正数同归于尽

按此逻辑，最后栈的大小其实就是逃生成功的正数个数postive，我们只要求和negative+postive即为题解。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const nums = (await readline()).split(" ").map(Number);

  // 负数逃生的总人数
  let negative = 0;
  // 正数缓冲栈，注意该栈只缓存正数
  const positive = [];

  // 正序遍历nums，遍历出来的num，相当于从左边逃生
  for (let num of nums) {
    // 输入异常时输出-1
    if (num == 0) return console.log(-1);

    if (num > 0) {
      // 如果左边逃出来的是正数，则缓冲到栈中
      positive.push(num);
    } else {
      // 如果左边逃出来的是负数
      while (true) {
        if (positive.length == 0) {
          // 如果栈为空，即没有正数，此时左边逃出来的负数直接逃生成功
          negative++;
          break;
        }

        // 如果栈不为空，则栈中有缓冲的正数，此时负数需要和栈顶正数进行pk
        const pk = num + positive.pop();

        if (pk > 0) {
          // 如果pk结果大于0，则负数逃生失败，栈顶的正数减少战斗力
          positive.push(pk);
          break;
        } else if (pk < 0) {
          // 如果pk结果小于0，则负数pk成功，此时需要继续和新栈顶正数pk，即进入下一轮
          num = pk;
        } else {
          // 如果pk结果为0，则同归于尽
          break;
        }
      }
    }
  }

  // 最终逃生成功的人数：negative即负数逃生成功个数，positive.size()即正数逃生成功个数
  console.log(negative + positive.length);
})();

Java算法源码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    System.out.println(getResult(nums));
  }

  public static int getResult(int[] nums) {
    // 负数逃生的总人数
    int negative = 0;

    // 正数缓冲栈，注意该栈只缓存正数
    LinkedList<Integer> positive = new LinkedList<>();

    // 正序遍历nums，遍历出来的num，相当于从左边逃生
    for (int num : nums) {
      // 输入异常时输出-1
      if (num == 0) return -1;

      if (num > 0) {
        // 如果左边逃出来的是正数，则缓冲到栈中
        positive.addLast(num);
      } else {
        // 如果左边逃出来的是负数
        while (true) {
          if (positive.size() == 0) {
            // 如果栈为空，即没有正数，此时左边逃出来的负数直接逃生成功
            negative++;
            break;
          }

          // 如果栈不为空，则栈中有缓冲的正数，此时负数需要和栈顶正数进行pk
          int pk = num + positive.removeLast();

          if (pk > 0) {
            // 如果pk结果大于0，则负数逃生失败，栈顶的正数减少战斗力
            positive.addLast(pk);
            break;
          } else if (pk < 0) {
            // 如果pk结果小于0，则负数pk成功，此时需要继续和新栈顶正数pk，即进入下一轮
            num = pk;
          } else {
            // 如果pk结果为0，则同归于尽
            break;
          }
        }
      }
    }

    // 最终逃生成功的人数：negative即负数逃生成功个数，positive.size()即正数逃生成功个数
    return negative + positive.size();
  }
}

Python算法源码

# 输入获取
nums = list(map(int, input().split()))


# 算法入口
def getResult():
    # 负数逃生的总人数
    negative = 0
    # 正数缓冲栈，注意该栈只缓存正数
    positive = []

    # 正序遍历nums，遍历出来的num，相当于从左边逃生
    for num in nums:
        # 输入异常时输出-1
        if num == 0:
            return -1

        if num > 0:
            # 如果左边逃出来的是正数，则缓冲到栈中
            positive.append(num)
        else:
            # 如果左边逃出来的是负数
            while True:
                if len(positive) == 0:
                    # 如果栈为空，即没有正数，此时左边逃出来的负数直接逃生成功
                    negative += 1
                    break

                # 如果栈不为空，则栈中有缓冲的正数，此时负数需要和栈顶正数进行pk
                pk = num + positive.pop()

                if pk > 0:
                    # 如果pk结果大于0，则负数逃生失败，栈顶的正数减少战斗力
                    positive.append(pk)
                    break
                elif pk < 0:
                    # 如果pk结果小于0，则负数pk成功，此时需要继续和新栈顶正数pk，即进入下一轮
                    num = pk
                else:
                    # 如果pk结果为0，则同归于尽
                    break

    # 最终逃生成功的人数：negative即负数逃生成功个数，positive.size()即正数逃生成功个数
    return negative + len(positive)


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>

#define MAX_SIZE 30001

int getResult(int* nums, int nums_size);

/*
 * 栈结构定义（基于线性表）
 * 容器 stack 数组，容量上限MAX_SIZE
 * 栈中元素个数 stack_size
 * 压栈操作 stack_push
 * 弹栈操作 stack_pop
 */
int stack[MAX_SIZE];
int stack_size = 0;

void stack_push(int ele)
{
    if(stack_size < MAX_SIZE) {
        stack[stack_size++] = ele;
    }
}

int stack_pop()
{
    if(stack_size > 0) {
        return stack[--stack_size];
    }
}

// 程序入口
int main()
{
    int nums[MAX_SIZE];
    int nums_size = 0;
    while(scanf("%d", &nums[nums_size++])) {
        if(getchar() != ' ') break;
    }

    printf("%dn", getResult(nums, nums_size));

    return 0;
}

// 核心代码
int getResult(int* nums, int nums_size)
{
    // 负数逃生的总人数
    int negative = 0;

    // 正序遍历nums，遍历出来的num，相当于从左边逃生
    for(int i=0; i<nums_size; i++) {
        int num = nums[i];

        // 输入异常时输出-1
        if(num == 0) return -1;

        if(num > 0) {
            // 如果左边逃出来的是正数，则缓冲到栈中
            stack_push(num);
        } else {
            while(1) {
                // 如果左边逃出来的是负数
                if(stack_size == 0) {
                    // 如果栈为空，即没有正数，此时左边逃出来的负数直接逃生成功
                    negative++;
                    break;
                }

                // 如果栈不为空，则栈中有缓冲的正数，此时负数需要和栈顶正数进行pk
                int pk = num + stack_pop();

                if(pk > 0) {
                    // 如果pk结果大于0，则负数逃生失败，栈顶的正数减少战斗力
                    stack_push(pk);
                    break;
                } else if(pk < 0) {
                    // 如果pk结果小于0，则负数pk成功，此时需要继续和新栈顶正数pk，即进入下一轮
                    num = pk;
                } else {
                    // 如果pk结果为0，则同归于尽
                    break;
                }
            }
        }
    }

    // 最终逃生成功的人数：negative即负数逃生成功个数，stack_size即正数逃生成功个数
    return negative + stack_size;
}