#5467. 「eJOI2025」反应 题解

问题分析

从某个起点 $S$ 开始执行实验，温度初始为 $0$，每个实验 $i$ 先改变温度 $D_i$，然后检查温度是否 $\geq T_i$。求最大可能反应次数。

关键转换

设前缀和 $prefix[i] = \sum_{k=0}^i D_k$，从 $S$ 开始到 $i$ 的温度为 $prefix[i] - prefix[S-1]$（设 $prefix[-1]=0$）。

反应条件：$prefix[i] - prefix[S-1] \geq T_i$

即：$prefix[i] - T_i \geq prefix[S-1]$

令 $A[i] = prefix[i] - T_i$，问题转化为：对每个 $S$，求满足 $i \geq S$ 且 $A[i] \geq prefix[S-1]$ 的 $i$ 的数量。

算法思路

从右向左扫描，维护单调栈。栈中存储 $(A[i], count)$，其中 $count$ 表示从 $i$ 开始能发生的反应次数。

对于每个位置 $i$：

1. 弹出栈中所有 $A[j] \geq prefix[i-1]$ 的元素，累加它们的 $count$
2. 如果 $A[i] \geq prefix[i-1]$，$count$ 加 $1$
3. 将 $(A[i], count)$ 压栈，保持栈单调递增

代码实现

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int reactions(int N, vector<int> D, vector<long long> T) {
    vector<long long> prefix(N);
    prefix[0] = D[0];
    for (int i = 1; i < N; i++)
        prefix[i] = prefix[i-1] + D[i];
    
    vector<long long> A(N);
    for (int i = 0; i < N; i++)
        A[i] = prefix[i] - T[i];
    
    int ans = 0;
    stack<pair<long long, int>> st;
    
    for (int i = N-1; i >= 0; i--) {
        long long threshold = i > 0 ? prefix[i-1] : 0;
        
        int cnt = 0;
        while (!st.empty() && st.top().first >= threshold) {
            cnt += st.top().second;
            st.pop();
        }
        
        if (A[i] >= threshold) cnt++;
        ans = max(ans, cnt);
        
        if (st.empty() || A[i] < st.top().first) {
            st.push({A[i], cnt});
        } else {
            auto top = st.top();
            st.pop();
            st.push({A[i], top.second + cnt});
        }
    }
    
    return ans;
}

复杂度分析

• 时间复杂度：$O(N)$，每个元素入栈出栈一次
• 空间复杂度：$O(N)$

样例验证

样例1

D = {1,1,-3,1,1}, T = {1,3,5,1,2}
最大反应次数 = 2

样例2

D = {1,-3,0,3,2}, T = {0,-2,-1,0,3}
最大反应次数 = 4