枚举 + 优化（8）—— 前缀和 2

例 3 题目链接：hihoCoder1534展开目录

这道题要注意一下数据范围。首先 N 小于等于 10 万。其次 $A_i$，也就是数组中每个数的值，是在负 100 万到正 100 万之间。假如这里 $A_i$ 都是正整数的话，那么总共的划分方法不会太多，因为随着 p 增大，第一段的和 S1 是不断增大的

但是因为这里 $A_i$ 有可能是 0，也有可能是负数，所以划分方法可能非常多。例如有可能数据是 10 万个 $A_i$ 全都是 0。这样随便一个划分都是满足条件的。答案是 C (99999, 2)，甚至超过了 int 范围

我们看一下样例，A 数组是 [3, 2, 1, 0, 2]。一共有 3 种切分方法：第一种是 3|2|1 0 2，3 单独一组，2 单独一组，然后 1 0 2 一组，三段的和依次是 3，2，3；第二种是 3|2 1|0 2|，3 单独一组，2 和 1 一组，0 2 一组，三段的和依次是 3，3， 2；第三种是 3|2 1 0|2，3 单独一组，2 1 0 一组，0 单独一组，三段的和依次是 3 3 2

思路展开目录

这道题一个基本的思路就是枚举 3 段的断点 p 和 q，然后求出来 3 段的和 S1, S2 和 S3。然后判断 S1，S2 和 S3 是不是满足题目要求，也就是相差不超过 1。如果满足条件就给答案累加 1。因为这里 S1，S2 和 S3 都是部分和，所以可能用前缀和来计算。但是在此之前，我们需要一个函数来判断三段和是否满足条件，如果满足条件就让结果 + 1。伪代码如下：

Ok(S1,S2,S3):
If |S1 - S2| <= 1 and |S1 - S3| <= 1 and |S2 - S3| <= 1
    return true
return false

然后我们预处理前缀和，以及进行枚举。伪代码如下：

//预处理前缀和
S[0] = 0
For i = 1...N
    S[i] = S[i - 1] + A[i]
//枚举+判断
Ans = 0
For p = 1...N-2
    For q = p+1...N-1
        S1 = S[p]

上面这个伪代码预处理前缀和的复杂度是 $O (N)$。后面枚举 pq 的复杂度是 $O (N^2)$。对于确定的 pq，判断三段和是不是满足条件是 $O (1)$。所以整体复杂度是 $O (N^2)$。至此，题目中 70% 的分数应该能拿到了，还有 30% 需要优化

优化展开目录

优化的方法当然还是从枚举入手，我们假设只枚举 q，也就是最后一段的断点。我们来分析一下这时候我们知道哪些信息，距离我们要的答案还有多远

看上图，假设 A 数组是 [3, 2, 1, 0, 2]，然后我们枚举 q=N-1，也就是第三段只包含 A [N]=2 这一个数。在 q 已经确定的情况下，可以知道 S3 的值。比如上面的例子中 S3=2。根据题目要求 S1、S2 和 S3 的差不能超过 1。所以对于一个合法的切分方案，S1 的取值只可能是 S3-1, S3, S3+1 三种，也就是 1，2，3

但是由于 S1+S2+S3 的和是整个数组的和，也就是 8。所以 S1 的三种取值不见得都能成立。比如 S1=1 这种情况，由于 S3=2 是确定的，所以 S2 一定等于 8-1-2=5。这是 S2 与 S3 相差超过 1，不符合题目要求。所以 S1=1 这种情况不成立。同理 S1=2 也是不成立的。但是 S1=3 是成立的，因为这时 S2 的值是 8-3-2=3。S2 与 S1 和 S3 相差都不超过 1

在 S [1], S [2] 和 S [3] 三个前缀和中，有几个的值是 3。因为每有一个前缀和的值是 3，都等价于找到了一种满足条件的切分方案：我们把这个前缀作为第一段，它的和等于 3；剩下的就是第二段，它的和一定是 3

实际例子中我们可以看上图，绿色的数组是前缀和。S [1], S [2], S [3] 分别是 3,5,6，只有 S [1]=3。所以 q=N-1 这种情况下，只有一种切分方案：3|2 1 0|2

上面是 q=N-1 的情况，我们再枚举 q=N-2 的情况，如下图：
S3 还是等于 2。S1 的可能取值还是 S3-1，S3，S3+1，也就是 1，2，3。其中只有 S1=3 时，S2 的值满足题目要求。所以我们的问题变成 S [0] 和 S [1] 中，有几个前缀和等于 3？
因为前缀和 S [1]=3, S [2]=5，所以还是只有 S [1]=3 一个解。于是 q=N-2 这种情况下，也只有一种切分方案：3|2 1|0 2

最后一种情况是 q=N-3 的时候：
这时 S3 值是 3。于是 S1 的取值范围是 S3-1, S3, S3+1，也就是 2, 3, 4。S1=2 是成立的，因为这时 S2=8-2-3=3，{2, 3, 3} 相差都不超过 1。S1=3 也是成立的，因为这时 S2=8-3-3=2，{3, 2, 3} 相差都不超过 1。S1=4 是不成立的。于是我们的问题变成，前缀和 S [0] 中，有几个前缀和的值是 2，有几个前缀和的值是 3
这时只有 S [1]=3 一个前缀和满足条件，所以 q=N-3 时，只有一组划分方法：3|2|1 0 2

上面我们就把样例的 3 种划分方法都求出来了。我们回顾一下上面的思路，基本就是从 N-1 到 2 枚举 q，对于每一个 q，我们都要求一类问题的解：

q = N-1时，前缀和S[1], S[2], … S[N-2]中有几个前缀和的值是X？（这里X可能是S3-1， S3， S3+1）<br>
q = N-2时，前缀和S[1], S[2], … S[N-3]中有几个前缀和的值是X？（这里X可能是S3-1， S3， S3+1）<br>
…
q = 2时，前缀和S[1]中有几个前缀和的值是X？（这里X可能是S3-1， S3， S3+1）

当然上面枚举 q 的过程中 S3 的值会变化，另外注意我们关心的前缀和集合也在变短。对于这一类问题，就是一堆前缀和中，有几个 X，我们当然可以用哈希表来实现。使得每次询问的复杂度都是 O (1) 的。具体来说，我们可以用 unordered_map<long long, int> cnt 来保存每个值出现了几次，例如 cnt [3] 的值表示前缀和是 3 的有几个。注意这里 key 的类型是 long long，因为前缀和可能超过 int 范围

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
int n,a[100001];
long long s[100001],ans = 0;
unordered_map<long long,int> cnt;

bool ok(long long s1,long long s2,long long s3)
{
    if(abs(s1 - s2) <= 1 && abs(s1 - s3) <= 1 && abs(s2 - s3) <= 1)
        return true;
    return false;
}

int main()
{
    cin >> n;
    s[0] = 0;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
        if(i < n)
            cnt[s[i]]++;
    }
    long long s3 = 0;
    for(int q = n - 1;q >= 2;q--)
    {
        s3 += a[q + 1];
        cnt[s[q]]--;
        for(long long s1 = s3 - 1;s1 <= s3 + 1;s1++)
        {
            long long s2 = s[n] - s1 - s3;
            if(ok(s1,s2,s3))
                ans += cnt[s1];
        } 
    }
    cout << ans;
    return 0;
}

第二次作业 hihocoder 1604展开目录

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000100;
int A[N];
int main()
{
    int n,j;
    cin >> n; 
    int ans = 0; 
    for(int i = 0;i < n;i++) 
        cin >> A[i];
    //从最后一天开始枚举 
    for(int i = n - 1;i >= 0;i = j)
    {
        for(j = i - 1;j >= 0;j--)//j从i的前一天开始一直向前枚举 
        {
            if(A[j] < A[i])//如果前面有价格比今天低的 
                ans += A[i] - A[j];//第j天买入，第i天卖出，赚取利润 
            else
                break;
        }
    }
    cout << ans;
    return 0;
}

这段代码都比较好理解，唯一有一个地方，就是第 16~21 行，尤其是 20，21 行，很多人可能会困惑，为什么 A[j]>=A[i] 就要 break，看下面的图讲解，可能更好理解
一开始 i 指向 N-1，也就是末尾的位置，j 指向 i 的前面一位，假如不 break，而是直接跳过这个值，程序继续执行下去，最后算得的 ans 应该是 2+1+4+3+7=17。如果 break，那么程序就会变成下图所示：

这种情况下算得的 ans 是 3+2+5+4+8=22。这是为什么？我们仔细分析一下原因：

1. 假设 A [i] 前面的所有数都比 A [i] 大，而且越往前越大，那 ans 最大也就是 0 了，因为股票的价格随着时间越往后越小，所以买股票一定是亏的，干脆不买，那就是 0
   
2. 如果排除第一种情况，也就是说，你在第 i 天买的股票后面总有一天的价格会比 A [i] 大，对于这种情况，就以上面的图来举例，假设第一天你买股票，那么第二天你是卖掉第一天的股票还是买呢？（什么都不干肯定是最亏的，这我们就不考虑了）假设你卖，那么你就变相相当于损失了 4，为什么是 4，如果你买了 5，那你在 9 可以卖掉 5，但是如果你不买，你不就没有卖的了么，1 在哪都可以卖，所以你干嘛不买 5 呢
3. 关于往前移动的问题，首先我们知道，假设 A [i]=3，如果 A [i-1]>A [i]，因为 A 数组都是正整数，所以 A [i-1] 最小也可以是 A [i]+1，那么所有股票在 A [i-1] 卖掉的钱都比 A [i] 至少多 1
   

如果你还有疑问，想想上图这种情况，或许你就会豁然开朗