题目理解

本题要求我们根据给定的字符串s和数组a，通过最少的修改次数使数组满足字符串的匹配要求。字符串中的每个字符对应数组中的一个元素，具体要求如下：

• '0'：对应元素必须≤0
• '1'：对应元素必须≥0
• 'Z'：对应元素必须=0，且左右相邻元素乘积≥0（边界除外）

解题思路

基本处理步骤

1. 遍历处理非Z字符：首先处理所有非Z的位置，检查是否满足条件，不满足则修改并计数
2. 处理Z字符：对于每个Z字符：
   • 必须将其设为0（如果不为0则修改）
   • 检查左右相邻元素的乘积是否为负（即符号相反）
   • 如果乘积为负，则需要修改其中一个元素（选择修改次数较少的方案）

关键点分析

• 贪心策略：在处理Z字符的相邻元素乘积为负时，我们采用贪心策略，选择修改成本较低的相邻元素
• 边界条件：当Z字符在数组首尾时，不需要检查乘积条件
• 效率优化：由于n可能很大(2×10^5)，算法必须保持O(n)的时间复杂度

复杂度分析

• 时间复杂度：O(n)，我们只对数组进行一次遍历，每个元素最多被处理两次（一次自身检查，一次作为Z的邻居）
• 空间复杂度：O(1)，除了输入数据外，只使用了常数级别的额外空间

代码实现

Python代码

n = int(input().strip())
s = input().strip()
a = list(map(int, input().strip().split()))
ans = 0 
 
for i in range(n):
    if s[i] == '0':
        if a[i] > 0:  # 不满足条件需要修改 
            a[i] = 0  # 修改为0是最稳妥的选择 
            ans += 1 
    elif s[i] == '1':
        if a[i] < 0:  # 不满足条件需要修改 
            a[i] = 0 
            ans += 1 
    elif s[i] == 'Z':
        if a[i] != 0:  # Z必须为0 
            a[i] = 0 
            ans += 1 
        # 检查相邻元素乘积是否小于0 
        if i > 0 and i < n - 1 and a[i-1] * a[i+1] < 0:
            # 贪心选择：修改其中一个元素为0 
            ans += 1 
            a[i+1] = 0  # 修改后一个元素（可以改为前一个，结果相同）
            
print(ans)

Java代码

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符 
        String s = scanner.nextLine();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '0') {
                if (a[i] > 0) {  // 不满足条件需要修改 
                    a[i] = 0;
                    ans++;
                }
            } else if (c == '1') {
                if (a[i] < 0) {  // 不满足条件需要修改 
                    a[i] = 0;
                    ans++;
                }
            } else if (c == 'Z') {
                if (a[i] != 0) {  // Z必须为0 
                    a[i] = 0;
                    ans++;
                }
                // 检查相邻元素乘积是否小于0 
                if (i > 0 && i < n - 1 && 1L * a[i-1] * a[i+1] < 0) {
                    // 贪心选择：修改其中一个元素为0 
                    ans++;
                    a[i+1] = 0;  // 修改后一个元素 
                }
            }
        }
        System.out.println(ans);
    }
}

C++代码

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0') {
            if (a[i] > 0) {  // 不满足条件需要修改 
                a[i] = 0;
                ans++;
            }
        } else if (s[i] == '1') {
            if (a[i] < 0) {  // 不满足条件需要修改 
                a[i] = 0;
                ans++;
            }
        } else if (s[i] == 'Z') {
            if (a[i] != 0) {  // Z必须为0 
                a[i] = 0;
                ans++;
            }
            // 检查相邻元素乘积是否小于0 
            if (i > 0 && i < n - 1 && 1LL * a[i-1] * a[i+1] < 0) {
                // 贪心选择：修改其中一个元素为0 
                ans++;
                a[i+1] = 0;  // 修改后一个元素 
            }
        }
    } 
    cout << ans << endl;
    return 0;
}

题目内容

小歪拿到了一个长度为 $n$，仅由字符 $'0’$、$'1’$和$'Z’$组成的字符串 $s_1s_2…s_n$。据说，这个字符串是用来匹配数组的。

我们称由 $n$ 个整数组成的数组{$a_1,a_2,...,a_n$}满足匹配字符串 $s= s_1s_2…s_n$ 的要求，当且仅当对于每个 $i(1≦i≦n)$有:

• $s_i$ 为 $'0'$ 时，$a_i≦0$；

• $s_i$ 为 $'1'$时，$a_i≧0$；

• $s_i$ 为 $'Z'$ 时，$a_i=0$，且 $a_{i-1}×a_{i+1}≧0$（如果 $i=1$ 或 $i=n$ ，则没有这个限制）。

你可以对数组中的任意元素进行修改，每个修改操作可以将该元素改为任意整数。求最少需要修改多少个元素，使得修改后的数组满足上述匹配要求。

输入描述

第一行输入一个整数 $n(1 ≤ n < 2× 10^5)$代表匹配长度。

第二行输入一个长度为 $n$ 的字符串 $s$，字符串仅由 $'0’$、$'1'$ 和 $'Z'$三种字符组成。

第三行输入 $n$ 个整数 $a_1,a_2,...,an_(-10^6 ≦ a_i≦10^6)$ 代表数组中的元素。

输出描述

输出一个整数，代表最少需要修改的元素个数。

样例1

输入

4
Z0Z0
-1 -2 3 4

输出

3

说明

在这个样例中:

对于第一个位置，由于 $s_1='Z'$，所以 $a_1$ 应当 $= 0$，将其修改。

对于第二个位置，由于 $s_2 ='0’$，所以 $a_2$ 应当 $≤ 0$，此时, $a_2$ 已经满足条件，不需要修改。

对于第三个位置，由于 $s_3 ='Z’$，所以 $a_3$ 应当 $= 0$，将其修改

对于第四个位置，由于 $s_4 ='0’$，所以 $a_4$ 应当 $≤ 0$，不妨将其修改为 $-4$。

至此，数组修改了 $3$ 次，为 {$0,-2,0,-4$}。检查每一个 $'Z’$，发现：

对于 $S_1$ 的 $'Z’$，没有额外条件;

而对于 $s_3$ 的 $'Z’$，此时已经有 $a_2 × a_4 ≥0$ 满足条件。

所以数组被 $s$ 匹配。我们可以证明，在这个样例中，至少需要修改 $3$ 个元素。

样例2

输入

3
01Z
-9 6 0

输出

0