[B3799 [NICA #1] 序列]

FallingFYC_ · 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; 
}

评测记录