AcWing 3956. 截断数组（每日一题）

思路1

构建前缀和数组分别使用三个指针截三段, i < j <k 如果a[i] == a[j] - a[i] == a[k] - a[j]

并且k == n 则认为我们已经分为三段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;
const int N = 10e5 + 10;
int n, ret;
int a[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
        
    for(int i = 1; i<= n; i++)
        a[i] = a[i] + a[i - 1];
    
    for(int i = 1; i <= n; i++)
    {
        int j = i + 1;
        int sum = a[i];
        while(j <= n && a[j] != 2 * sum) j++;
        int k = j + 1;
        while(k <= n && a[k] != 3 * sum) k++;
        if(i < j < k && k == n) 
            ret++;
    }
    
    cout << ret;
    return 0;
}

通过上述代码我们发现, 题目成立的充要条件是每一段都等于 a[n] / 3 由此产生思路2

思路2

找到a[n] / 3 的点, 当第一个指针到达 三分之一点的时候我们选取后在选择第二个指针j == 2 * a[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;
const int N = 10e5 + 10;
int n, ret;
int a[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
        
    for(int i = 1; i<= n; i++)
        a[i] = a[i] + a[i - 1];
    
    for(int i = 1; i <= n; i++)
    {
        if(3 * a[i] == a[n])
        {
            int j = i + 1;
            while(j < n) 
            {
                if(2 * a[i] == a[j]) ret ++;
                j++;
            }
        }
    }
    
    cout << ret;
    return 0;
}

上述代码时间复杂度为O(n^2) 某些答案会超时, 检查代码后会发现, 前缀和数组中会出现很多相同的值, (错误的思路是使用二分优化, 因为不能保证数据中不会出现负数, 所以这里不能用二分)

这是一个错误的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
using namespace std;
const int N = 10e5 + 10;
int n;
long long ret;
int a[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
        
    for(int i = 1; i<= n; i++)
        a[i] = a[i] + a[i - 1];
    
    for(int i = 1; i <= n; i++)
    {
        if(3 * a[i] == a[n])
        {
            int sum = 2 * a[i];
            
            int l = i + 1, r = n - 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(a[mid] >= sum) r = mid;
                else l = mid + 1;
            }
            int left = r;
            
            l = i + 1, r = n - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(a[mid] <= sum) l = mid;
                else r = mid + 1;
            }
            int right = l;
            if(i < left && right < n && a[right] == sum && a[left] ==sum) ret += right - left + 1;

        }
    }
    
    cout << ret;
    return 0;
}

最总解题思路

首先我们要找到 三分之一点, 然后从前向后遍历数组中的每一个点, 且一倍点和二倍点必须成对出现, 累加最后成对出现的次数,即是最终的答案.

代码中注释的部分容易出现坑, 如果先累加一倍点的数量再累加二倍点的数量的话, 出现相同的值,比如0, 会在相同的位置进行两次累加计算, 显然不符合题意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
const int N = 10e5 + 10;
int n;
long long ret;
int a[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
        
    for(int i = 1; i<= n; i++)
        a[i] = a[i] + a[i - 1];
    
    if(a[n] % 3 != 0 || n < 3) cout << 0;
    else
    {
        int tar = a[n] / 3;
        int t = 0;
        for(int i = 1; i < n; i++)
        {
            // 一定要先判定二倍点再判定一倍点
            // 如果一个点既是二倍点也是一倍点, 那么会在相同的位置进行分割, 显然不符合题意.
            if(a[i] == 2 * tar) ret += t;
            //  ret 一定使用+= 因为每一个二倍点都可以和之前每一个一倍点组合
            if(a[i] == tar) ++t;
        }
        cout << ret;
    }
    
    return 0;
}