题解 | #符文激活#

题目链接

题目描述

在一座失落的古老神殿中，祭坛可以看作是一个长度为 $n$ 的序列，有些位置上刻有远古符文（用 1 表示），而另一些位置则是空的（用 0 表示）。你可以在任何空的位置上放置一颗能量水晶。一个远古符文能够被成功激活，当且仅当其左侧或右侧的相邻位置上放置了一颗能量水晶。

任务是找出一种放置能量水晶的方案，使得所有的远古符文都被激活，并且使用的能量水晶数量最少。如果无法激活所有符文，则返回-1。

输入:

第一行是一个正整数 $n$ ，代表祭坛序列的长度。
第二行是 $n$ 个整数（0或1），表示祭坛序列 $runes$ 。

输出:

一个整数，表示所需的最少能量水晶数量。如果无法激活所有符文，则输出-1。

解题思路

这是一个典型的贪心算法问题。我们的目标是用最少的水晶激活所有符文。

我们可以从左到右遍历整个符文序列。当我们遇到一个符文（值为 1）时，需要决定如何激活它。

检查是否已激活：首先，我们需要检查当前符文是否已经被激活。因为我们是从左到右遍历的，所以一个符文只可能被其左侧的水晶激活。我们用一个辅助数组 $has\_crystal$ 来记录水晶的放置位置。如果符文在 $i$ 位置，我们检查 $has\_crystal[i-1]$ 是否为真即可。
贪心选择：如果当前符文尚未被激活，我们就必须放置一颗新的水晶。我们有两个选择：放在左边（ $i-1$ ）或右边（ $i+1$ ）（前提是这些位置为空）。为了使水晶的效用最大化，贪心的策略是优先将其放置在符文的右侧（ $i+1$ ）。这是因为，放置在 $i+1$ 的水晶不仅能激活当前 $i$ 位置的符文，还有可能激活 $i+2$ 位置的符文，从而覆盖更多的未来需求。
次优选择：如果右侧（ $i+1$ ）无法放置水晶（比如 $i$ 是序列的最后一个元素，或者 $i+1$ 位置本身也是一个符文），我们只能退而求其次，尝试将其放置在左侧（ $i-1$ ）。
无解情况：如果一个符文的左右两侧都无法放置水晶，那么这个符文就永远无法被激活，整个任务失败，应返回-1。

我们通过一次遍历，根据这个贪心策略完成所有符文的激活，并计数所使用的水晶数量，即可得到最终答案。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> runes(n);
    for (int i = 0; i < n; ++i) {
        cin >> runes[i];
    }

    int count = 0;
    // 记录每个位置是否放置了水晶
    vector<bool> has_crystal(n, false);

    for (int i = 0; i < n; ++i) {
        // 只关心符文的位置
        if (runes[i] == 1) {
            // 检查此符文是否已被其左侧的水晶激活
            if (i > 0 && has_crystal[i - 1]) {
                continue;
            }

            // 如果未激活，尝试放置新水晶
            // 贪心策略：优先在右侧放置，因为这样可能激活未来的符文
            if (i + 1 < n && runes[i + 1] == 0) {
                has_crystal[i + 1] = true;
                count++;
            } 
            // 如果右侧不行，尝试在左侧放置
            else if (i > 0 && runes[i - 1] == 0) {
                // 此时 has_crystal[i-1] 必定是 false, 否则第一个if就会通过
                has_crystal[i - 1] = true;
                count++;
            } 
            // 如果左右都无法放置水晶，则无解
            else {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << count << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] runes = new int[n];
        for (int i = 0; i < n; i++) {
            runes[i] = sc.nextInt();
        }

        int count = 0;
        // 记录每个位置是否放置了水晶
        boolean[] hasCrystal = new boolean[n];

        for (int i = 0; i < n; i++) {
            // 只关心符文的位置
            if (runes[i] == 1) {
                // 检查此符文是否已被其左侧的水晶激活
                if (i > 0 && hasCrystal[i - 1]) {
                    continue;
                }

                // 如果未激活，尝试放置新水晶
                // 贪心策略：优先在右侧放置
                if (i + 1 < n && runes[i + 1] == 0) {
                    hasCrystal[i + 1] = true;
                    count++;
                } 
                // 如果右侧不行，尝试在左侧放置
                else if (i > 0 && runes[i - 1] == 0) {
                    hasCrystal[i - 1] = true;
                    count++;
                } 
                // 如果左右都无法放置，则无解
                else {
                    System.out.println(-1);
                    return;
                }
            }
        }
        System.out.println(count);
    }
}

n = int(input())
runes = list(map(int, input().split()))

count = 0
# 记录每个位置是否放置了水晶
has_crystal = [False] * n
possible = True

for i in range(n):
    # 只关心符文的位置
    if runes[i] == 1:
        # 检查此符文是否已被其左侧的水晶激活
        if i > 0 and has_crystal[i - 1]:
            continue
        
        # 如果未激活，尝试放置新水晶
        # 贪心策略：优先在右侧放置
        if i + 1 < n and runes[i + 1] == 0:
            has_crystal[i + 1] = True
            count += 1
        # 如果右侧不行，尝试在左侧放置
        elif i > 0 and runes[i - 1] == 0:
            has_crystal[i - 1] = True
            count += 1
        # 如果左右都无法放置，则无解
        else:
            possible = False
            break

if possible:
    print(count)
else:
    print(-1)

算法及复杂度

算法：贪心算法
时间复杂度：我们只需要对长度为 $n$ 的符文序列进行一次遍历，因此总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：我们使用了一个长度为 $n$ 的辅助数组 $has\_crystal$ 来记录水晶的放置位置，因此总空间复杂度为 $\mathcal{O}(n)$ 。