💡牛客匹配数组与字符串 S（贪心 + 强制符号控制）题解 + 易错点分析

原题链接：牛客竞赛105623-C题
标签：贪心、符号控制、连续条件处理
作者：@wwwqqqzzz

✨题目简述

我们有一个整数数组 a[1..n] 和一个仅由 '<', '>', 'Z' 组成的字符串 S[1..n]，其中：

• 若 S[i] == '<'，则需 a[i] < 0
• 若 S[i] == '>'，则需 a[i] > 0
• 若 S[i] == 'Z'，则需 a[i-1] * a[i] > 0，即两个数非零同号

你可以任意修改 a[i] 的值，每次修改算一次操作，问最少多少次修改能满足所有条件。

❗常见误区（我踩过的坑）

if (S[i] == '<' && a[i] >= 0) {
    cnt++;
    a[i] *= -1;
}

这看似没毛病，其实处理不了 a[i] == 0 的情况！

• 0 * -1 == 0，仍然不满足 < 0 或 > 0
• 会导致判断错误，AC 失败！

✅贪心 + 强制符号设置（AC解法）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        string s; cin >> s;
        int cnt = 0;

        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] == '<') {
                if (a[i] >= 0) {
                    a[i] = -1; // 强制为负数
                    cnt++;
                }
            }
            else if (s[i - 1] == '>') {
                if (a[i] <= 0) {
                    a[i] = 1;  // 强制为正数
                    cnt++;
                }
            }
            else if (s[i - 1] == 'Z') {
                if (a[i - 1] * a[i] <= 0) { // 不同号或0
                    cnt++;
                    a[i] = (a[i - 1] == 0 ? 1 : a[i - 1]); // 贪心设为同号
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}