高效求解子数组中前x大元素之和的方法

架构老林

2026-6-26

高效解决子数组最大x元素和查询问题

问题描述

给定一个1-indexed的正整数数组，需处理多组查询，每组查询要求：计算子数组[1,y]中最大的x个元素之和。数组无序，x和y随每组查询动态变化，输入无需校验，时间限制为1秒（约支持1亿次操作），且支持离线查询。

当前解法的瓶颈

当前解法为每次查询时对整个数组按元素值排序并保留索引，再选取索引≤y的前x个元素求和。单查询复杂度为O(N logN)，总复杂度O(QNlogN)。但由于N和Q均可达100,000，该解法速度过慢。

以下是基于priority_queue的慢解法代码：

int n; scanf("%d", &n);
priority_queue<pair<int, int>> pq;
for (int i = 1; i <= n; i++) {          // 读取数组并初始化优先队列
    int a; scanf("%d", &a);
    pq.push({a, i});
}

for (int i = 0; i < q; i++) {
    int x, y; scanf("%d %d", &x, &y);
    priority_queue<pair<int, int>> temp = pq;
    int c = 0, ans = 0;
    while (c < x) {
        // 移除不在目标子数组中的元素
        while (temp.top().second > y) temp.pop();    
        
        // 累加符合条件的元素
        c++;
        ans += temp.top().first*2;
        temp.pop();
    }

    printf("%d\n", ans);
}