2 条题解

  • -1
    @ 2023-11-15 18:40:53

    #include #include <unordered_map> #include

    using namespace std;

    int find_max_equal_subsequence_length(int n, const vector& arr) { // 将0转换为-1 vector modifiedArr(arr.begin(), arr.end()); for (int i = 0; i < n; ++i) { if (modifiedArr[i] == 0) { modifiedArr[i] = -1; } }

    // 计算前缀和数组
    vector<int> prefixSum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefixSum[i] = prefixSum[i - 1] + modifiedArr[i - 1];
    }
    
    // 创建一个unordered_map,用于存储每个前缀和第一次出现的位置
    unordered_map<int, int> prefixSumIndex;
    
    int maxLength = 0;
    
    for (int i = 0; i <= n; ++i) {
        // 如果当前前缀和已经在unordered_map中出现过,说明两次出现的位置之间的子数组男女人数相等
        if (prefixSumIndex.find(prefixSum[i]) != prefixSumIndex.end()) {
            maxLength = max(maxLength, i - prefixSumIndex[prefixSum[i]]);
        } else {
            // 如果当前前缀和第一次出现,记录其位置
            prefixSumIndex[prefixSum[i]] = i;
        }
    }
    
    return maxLength;
    

    }

    int main() { // 读取输入 int n; cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    // 计算并输出结果
    int result = find_max_equal_subsequence_length(n, arr);
    cout << result << endl;
    
    return 0;
    

    }

    信息

    ID
    1281
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    189
    已通过
    35
    上传者