【算法小白周赛1E】ET表题解与代码（算法与数据结构刷题计划）

题目链接：https://www.starrycoding.com/contest/3/E

题目描述

小e发明了一种奇怪的数据结构——ET表，这一奇怪的数据结构有以下两种奇怪的操作：

• 将前 $i$ 个数减去 $k$。
• 将后 $i$ 个数减去 $k$。

为了测试ET表的性能，小e找来了一个长度为 $n$ 数组 $a$，现在需要判断能否通过ET表的这两种操作将这个数组的每一个数都变成 $0$，以及最少的操作次数。

输入格式

第一行为一个正整数 $T$ ( $1\le T\le 10^6$ )，表示测试用例个数。

对于每个测试用例：

第一行为一个正整数 $n$ ( $1\le n\le 10^6$ )，表示数组长度；

第二行包含 $n$ 个正整数 $a_1\dots a_n$ ( $1\le a_i\le 10^6$ )

数据保证 $\sum n\le 10^6$。

输出格式

每个测试用例的输出一行：

• 如果可以通过一定次数的ET表操作使数组的所有元素都等于零，输出一个正整数，表示最少的操作次数。
• 否则输出 $-1$。

样例 #1

样例输入 #1

4
3
1 2 1
3
2 3 2
5
19 1 9 8 10
6
1 1 4 5 1 4

样例输出 #1

2
3
4
-1

说明/提示

对于样例第二组数据 $[2,3,2]$，

• 选择 $i=3,k=1$ 进行操作一，数组变为 $[1,2,1]$，
• 选择 $i=2,k=1$ 进行操作一，数组变为 $[0,1,1]$，
• 选择 $i=2,k=1$ 进行操作二，数组变为 $[0,0,0]$，

成功归零，共操作 $3$ 次。

对于样例第三组数据 $[19,1,9,8,10]$，

• 选择 $i=1,k=18$ 进行操作一，数组变为 $[1,1,9,8,10]$，
• 选择 $i=1,k=2$ 进行操作二，数组变为 $[1,1,9,8,8]$，
• 选择 $i=3,k=1$ 进行操作一，数组变为 $[0,0,8,8,8]$，
• 选择 $i=3,k=8$ 进行操作二，数组变为 $[0,0,0,0,0]$，

成功归零，共操作 $4$ 次。

对于样例第四组数据，无论如何也无法将其归零。

题解

其实所谓的ET表操作，其实就是对数组的某一长度的前、后缀进行区间减去某个数的操作，此时我们应该想到非常擅长进行区间操作的好东西——差分。

建立差分数组 $d$，对于数组 $[l,r]$ 的修改就等效于对差分数组的 $d_l$ 和 $d_{r+1}$ 进行修改，此时的ET表操作就变成了：

• 将 $d_1$ 减少 $k$，将 $d_{i+1}$ 增加 $k$，
• 将 $d_{n-i+1}$ 减少 $k$，将 $d_{n+1}$ 增加 $k$，

且此时 $d_{n+1}$ 对数组 $a$ 不会有任何影响，所以对它的操作可以忽略，而我们的最终目的——将数组 $a$ 归零也就等效于将 $d_1\dots d_n$ 归零。所以在判断是否可行是，我们只需要计算差分数组中所有小于 $0$ 的数的绝对值之和 $s$，将这个总和与 $d_1$ 进行比较，如果大于 $d_1$ 则说明无法完成归零。计算最少操作次数则贪心的只对 $d_2\dots d_n$ 中每个非 $0$ 的进行一次操作，最后特判一下进行了上述操作后 $d_1$ 是否已经归零，也就是 $s$ 是否等于 $d_1$ 来确定是否还要进行一次操作使 $d_1$ 归零。

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> d(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        d[i] = a[i] - a[i - 1]; // 差分
    }
    int s = 0, ans = 0;
    for (int i = 2; i <= n; i++)
    {
        if (d[i] < 0)
        {
            s += abs(d[i]); // 对于差分数组中小于0的进行操作一，
            ans++;          // 操作次数+1，并记录会对d[1]产生的影响
        }
        else if (d[i] > 0)
        {
            ans++; // 对于大于0的进行一次操作二
        }
    }
    if (s > d[1]) // d[1]不足以完成足够的操作一
    {
        cout << -1 << endl;
        return;
    }
    if (s < d[1]) // 当前进行的操作一不足以将d[1]归零
    {
        ans++;
    }
    cout << ans << endl;
    return;
}

StarryCoding - 编程开发新手村，非常适合新手小白的一个网站，推荐给大家~

5月1日晚上还有一场入门教育赛，欢迎来玩：https://www.starrycoding.com/contest/5