题解 | #逃脱神凛幻域#

题目链接

逃脱神凛幻域

题目描述

需要向前走出 $n$ 步才能逃脱幻域。由于空间内没有方向的概念，每一步向任何方向走都是等效的。

已知在第 $i$ 步（ $1 \le i \le n$ ）向东、南、西、北四个方向走所分别耗费的体力值。请找出一条总耗费体力最小的路径。

要求：

输出最小的总耗费体力。
输出对应的行走方案字符串（用 'E', 'S', 'W', 'N' 分别表示东南西北）。
当某一步的多个方向体力值均为最小值时，按照 东 > 南 > 西 > 北 的顺序取优先方向。

解题思路

这是一个典型的贪心算法问题。题目的核心在于，要走完 $n$ 步，并且每一步的选择（走哪个方向）是完全独立的，当前步骤的选择不会影响未来步骤的体力消耗情况。

因此，要使总的体力消耗最小，我们只需要确保每一步的体力消耗都是最小的。

算法流程：

数据存储：
- 读入总步数 $n$ 。
- 使用四个数组（或列表），分别存储 $n$ 步中每一步向东、南、西、北走的体力消耗。例如 cost_e[i], cost_s[i], cost_w[i], cost_n[i] 分别表示第 i+1 步向四个方向走的体力。
逐一决策：
- 初始化总消耗体力 total_cost = 0 和一个空的结果路径字符串 path。
- 使用一个循环，从第 1 步到第 $n$ 步 (即数组索引从 0 到 $n-1$ )。
- 在循环的每一步 i 中：
  
  a. 比较当前步骤 i 的四个方向的体力消耗值：cost_e[i], cost_s[i], cost_w[i], cost_n[i]。
  
  b. 找出这四个值中的最小值 min_cost。
  
  c. 将 min_cost 累加到 total_cost 中。
  
  d. 根据优先顺序确定方向：
  - 检查 cost_e[i] 是否等于 min_cost，如果是，则选择东方 'E'。
  - 否则，检查 cost_s[i] 是否等于 min_cost，如果是，则选择南方 'S'。
  - 否则，检查 cost_w[i] 是否等于 min_cost，如果是，则选择西方 'W'。
  - 否则，只能是北方 'N'。
  e. 将选定的方向字符追加到 path 字符串的末尾。
输出结果：
- 循环结束后，total_cost 就是最小的总耗费体力，path 就是对应的最优路径。依次输出它们。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;

    vector<long long> e(n), s(n), w(n), north(n);
    for (int i = 0; i < n; ++i) cin >> e[i];
    for (int i = 0; i < n; ++i) cin >> s[i];
    for (int i = 0; i < n; ++i) cin >> w[i];
    for (int i = 0; i < n; ++i) cin >> north[i];

    long long total_cost = 0;
    string path = "";

    for (int i = 0; i < n; ++i) {
        long long min_cost = min({e[i], s[i], w[i], north[i]});
        total_cost += min_cost;
        if (e[i] == min_cost) {
            path += 'E';
        } else if (s[i] == min_cost) {
            path += 'S';
        } else if (w[i] == min_cost) {
            path += 'W';
        } else {
            path += 'N';
        }
    }

    cout << total_cost << endl;
    cout << path << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        long[] e = new long[n];
        long[] s = new long[n];
        long[] w = new long[n];
        long[] north = new long[n];

        for (int i = 0; i < n; i++) e[i] = sc.nextLong();
        for (int i = 0; i < n; i++) s[i] = sc.nextLong();
        for (int i = 0; i < n; i++) w[i] = sc.nextLong();
        for (int i = 0; i < n; i++) north[i] = sc.nextLong();

        long totalCost = 0;
        StringBuilder path = new StringBuilder();

        for (int i = 0; i < n; i++) {
            long minCost = Math.min(Math.min(e[i], s[i]), Math.min(w[i], north[i]));
            totalCost += minCost;
            if (e[i] == minCost) {
                path.append('E');
            } else if (s[i] == minCost) {
                path.append('S');
            } else if (w[i] == minCost) {
                path.append('W');
            } else {
                path.append('N');
            }
        }

        System.out.println(totalCost);
        System.out.println(path.toString());
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        
        e = list(map(int, sys.stdin.readline().strip().split()))
        s = list(map(int, sys.stdin.readline().strip().split()))
        w = list(map(int, sys.stdin.readline().strip().split()))
        north = list(map(int, sys.stdin.readline().strip().split()))
        
        total_cost = 0
        path = []
        
        for i in range(n):
            costs = [
                ('E', e[i]),
                ('S', s[i]),
                ('W', w[i]),
                ('N', north[i])
            ]
            
            # 找到最小值
            min_cost = min(c[1] for c in costs)
            
            # 根据优先顺序选择方向
            chosen_direction = ''
            for direction, cost in costs:
                if cost == min_cost:
                    chosen_direction = direction
                    break
            
            total_cost += min_cost
            path.append(chosen_direction)
            
        print(total_cost)
        print("".join(path))

    except (IOError, ValueError):
        return

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：贪心算法
时间复杂度： $\mathcal{O}(N)$ ，其中 $N$ 是需要走的总步数。我们需要遍历每一步来做出最优选择。对于 $T$ 组测试数据，总复杂度是 $\mathcal{O}(T \cdot N)$ 。
空间复杂度： $\mathcal{O}(N)$ 。需要四个大小为 $N$ 的数组来存储每个方向在每一步的体力消耗。