自动搬运

查看原文

来自洛谷，原作者为

	FallingFYC_ 但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。

搬运于2025-08-24 21:15:07，当前版本为作者最后更新于2023-07-10 11:32:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题

细节决定成败。

分析&思路

要先明确一点：操作 2 就是让求出序列 $a$ 中的正整数之和（因为如果是负数则会让结果变小）。

一个暴力的做法是：

• 对于操作 1，用一个变量记录所需加上的数字之和。
• 对于操作 2，遍历一遍序列 $a$，将其中的每一项加上在当前操作之前所需加上的数字之和，判断这个数是否大于 $0$，是则在最终结果中加上此数，否则不加。

最坏情况下，这种方法的时间复杂度为 $O(mn)$。

代码：

#include <bits/stdc++.h>
using namespace std;
int n , m , a[500005] , opt , k;
long long add , ans;
int main()
{
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    while (m--)
    {
        cin >> opt;
        if (opt == 1) {cin >> k; add += k;}
        else
        {
            ans = 0;
            for (int i = 1 ; i <= n ; i++)
                if (a[i] + add > 0) ans += a[i] + add;
            cout << ans << endl;
        }
    }
    return 0; 
}

评测记录

不出所料，T 了 6 个点。

考虑优化。

操作 1 无需优化，来看操作 2。

对于操作 2，很容易想到一种基于暴力的优化：

1. 对序列 $a$ 排序。
2. 二分查找第一个大于 0 的数的下标，计为 $p$。
3. 累加序列 $a$ 中从下标为 $p$ 的数字到最后一个（预处理前缀和）。

这样优化的时间复杂度最坏为 $O(m \log n)$，空间复杂度为 $O(n)$。

注意：

1. 开 long long。
2. $p$ 要初始化成 $n + 1$（如果没有比 $0$ 大的数就会输出 $0$）。
3. 本题中所用的前缀和是倒序的。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n , m , a[500005] , opt , k , sum[500005] ,  add , ans;
signed main()
{
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    sort(a + 1 , a + n + 1);
    for (int i = n ; i >= 1 ; i--) sum[i] = a[i] + sum[i + 1];//倒序的前缀和
    while (m--)
    {
        cin >> opt;
        if (opt == 1) {cin >> k; add += k;}
        else
        {
            int p = n + 1;//这里的初始化很关键！
            int l = 1 , r = n , mid;
            while (l <= r)
            {
                mid = (l + r) / 2;
                if (a[mid] + add > 0) {p = mid; r = mid - 1;}
                else l = mid + 1;
            }
            ans = sum[p] + (n - p + 1) * add;
            //最后将大于0的数统一加上在当前操作之前所需加上的数字之和。
            cout << ans << endl;
        }
    }
    return 0; 
}

评测记录