C++ 算法实战：数字变换、矩阵优化与前缀和技巧

三、滑动窗口与前缀和

小红吃桃子，每天获得快乐值 $a_i$ 和羞耻值 $b_i$，效果持续 $k$ 天。要求找到开始吃桃子的日期，使得这 $k$ 天的总快乐值最大；若快乐值相同，则选择羞耻值最小的那一天。

思路解析

方法一：滑动窗口

这是一个典型的定长窗口问题。我们维护一个长度为 $k$ 的窗口，记录当前窗口内的快乐值和与羞耻值和。

当窗口向右移动时，只需减去离开窗口的元素，加上新进入窗口的元素。同时维护全局的最大快乐值 hMax 和对应的最小羞耻值 sMin。当遇到新的最大值或相同最大值下更小的羞耻值时，更新答案。

方法二：前缀和

既然需要频繁查询区间和，前缀和是另一个高效的选择。

预处理两个前缀和数组，分别存储快乐值和羞耻值的累积和。对于起始位置 $i$，区间和可以通过 prefix[i+k-1] - prefix[i-1] 在 $O(1)$ 时间内获取。这种方法同样避免了重复计算，且代码逻辑通常比滑动窗口更简洁。

注意边界情况，从 $i$ 开始必须有足够的天数，即 $i$ 的范围是 $[1, n-k+1]$。

代码实现：滑动窗口

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
long long h[N], s[N];

int main() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> s[i];
    
    int left = 1, right = 1;
    long long hSum = 0, sSum = 0;
    long long hMax = 0, sMin = 0;
    int ret = 0;
    
    while (right <= n) {
        hSum += h[right];
        sSum += s[right];
        
        while (right - left + 1 > k) {
            hSum -= h[left];
            sSum -= s[left];
            left++;
        }
        
        if (right - left + 1 == k) {
            if ((hSum > hMax) || (hSum == hMax && sSum < sMin)) {
                ret = left;
                hMax = hSum;
                sMin = sSum;
            }
        }
        right++;
    }
    
    cout << ret << endl;
    return 0;
}

代码实现：前缀和

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
long long h[N], s[N];
long long hSum[N], sSum[N];

int main() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        hSum[i] = hSum[i - 1] + h[i];
    }
    
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        sSum[i] = sSum[i - 1] + s[i];
    }
    
    int ret = 0;
    long long hMax = 0, sMin = 0;
    
    for (int i = 1; i <= n - k + 1; i++) {
        long long numh = hSum[i + k - 1] - hSum[i - 1];
        long long nums = sSum[i + k - 1] - sSum[i - 1];
        
        if ((numh > hMax) || (numh == hMax && nums < sMin)) {
            ret = i;
            hMax = numh;
            sMin = nums;
        }
    }
    
    cout << ret << endl;
    return 0;
}

以上就是本次刷题的三道典型题目，涵盖了字符串处理、二维数组优化以及经典的滑动窗口与前缀和技巧。希望这些解析能帮助你更好地理解算法背后的逻辑。