算法标签：

贪心, 数据结构, 前缀和, 模拟,

题解

一、题目分析

这段C++代码主要实现了对一个整数数组的处理，通过某种特定的操作方式，计算并输出一个与数组元素相关的结果。程序会不断读取输入的数组长度 n 和数组元素值，当输入的 n 为 0 时，程序结束运行。处理逻辑是对数组中正数和负数进行配对处理，计算每次配对操作的代价，并将所有代价累加起来得到最终结果。

二、代码思路

1. 数据定义：
   • 定义宏 maxn 为 100005，用于限制数组 f 的大小。
   • 声明全局变量 n 表示数组的长度，f[maxn] 数组用于存储输入的整数序列。
2. 输入函数 input：该函数通过一个 for 循环，根据输入的数组长度 n，依次读取 n 个整数，并存储到数组 f 中。
3. 处理函数 work：
   • 初始化两个指针 i 和 j 都为 0，用于遍历数组，同时初始化变量 ans 为 0，用于存储最终的结果。
   • 进入一个无限循环，在循环内部：
     • 第一个内层 while 循环，找到数组中第一个大于 0 的元素，即 while (i < n && f[i] <= 0) i++;。
     • 第二个内层 while 循环，找到数组中第一个小于 0 的元素，即 while (j < n && f[j] >= 0) j++;。
     • 检查 j 或 i 是否超出数组范围，如果 j >= n 或 i >= n，则跳出循环，结束处理。
     • 计算 x 为当前正数 f[i] 和负数 f[j] 绝对值的较小值，即 int x = min(f[i], -f[j]);。
     • 根据 x 的值对 f[i] 和 f[j] 进行更新，f[i] -= x; 和 f[j] += x;。
     • 将本次操作的代价 x * abs(i - j) 累加到 ans 中，即 ans += x * abs(i - j);。
   • 循环结束后，输出最终的结果 ans。
4. 主函数 main：使用 while (scanf("%d", &n), n) 循环读取输入的数组长度 n，当 n 不为 0 时，调用 input 函数读取数组元素，然后调用 work 函数进行处理。当 n 为 0 时，结束循环，程序返回 0 结束运行。

三、代码实现

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;

#define maxn 100005

int n, f[maxn];

void input()
{
    for (int i = 0; i < n; i++)
        scanf("%d", &f[i]);
}

void work()
{
    int i = 0, j = 0;
    long long ans = 0;
    while (1)
    {
        while (i < n && f[i] <= 0)
            i++;
        while (j < n && f[j] >= 0)
            j++;
        if (j >= n || i >= n)
            break;
        int x = min(f[i], -f[j]);
        f[i] -= x;
        f[j] += x;
        ans += x * abs(i - j);
    }
    printf("%lld\n", ans);
}

int main()
{
    while (scanf("%d", &n), n)
    {
        input();
        work();
    }
    return 0;
}

四、复杂度分析

1. 时间复杂度：
   • 在 work 函数中，每次循环至少会使 i 或 j 向前移动一位，最多经过 2n 次循环（极端情况下，数组中正数和负数交替出现），每次循环内部的操作时间复杂度为常数级。
   • 输入函数 input 中，读取 n 个元素的时间复杂度为 $O(n)$。
   • 因此，总体时间复杂度为 $O(n)$，n 为数组的长度。
2. 空间复杂度：
   • 程序主要使用了一个长度为 maxn 的数组 f 来存储输入的整数序列，空间复杂度为 $O(n)$，n 为数组的长度。
   • 此外，还使用了一些简单的变量如 i、j、ans 等，这些变量的空间占用为常数级，对总体空间复杂度影响较小。
   • 所以，整个程序的空间复杂度为 $O(n)$。

五、注意事项

1. 输入数据的范围要符合数组 f 的大小限制，因为定义了 maxn 为 100005，如果输入的数组长度 n 超过这个值，可能会导致数组越界等错误。
2. 代码中使用了 long long 类型来存储最终结果 ans，这是因为在计算过程中可能会产生较大的数值，使用 long long 可以避免整数溢出的问题。在处理类似的数值计算时，要注意数据类型的选择。