题目分析与思路提示

1. 暴力法

用一个数组存储金榜。

• 每次插入：放入数组，排序，保留前 $K$ 个。
• 复杂度：每次操作 $O(K \log K)$ 或 $O(K)$。
• 总复杂度：$O(N \cdot K)$。
• 如果 $N=2 \times 10^5, K=10^5$，运算量达到 $2 \times 10^{10}$，超时。

2. 优化思路：优先队列 (Priority Queue)

我们需要频繁进行两个操作：

1. 找到并删除最小元素。
2. 插入新元素。

这正是 小根堆 (Min-Heap) 的拿手好戏。在 C++ STL 中，priority_queue 默认是大根堆，我们需要稍作修改使其成为小根堆。

算法流程：

1. 定义一个小根堆 pq。
2. 定义一个变量 sum 记录堆中元素的和。
3. 对于 Type 1 (新分数 $S$)：
   • 如果堆的大小 $< K$：
     • 直接入堆：pq.push(S)
     • 更新和：sum += S
   • 如果堆的大小 $== K$：
     • 比较 $S$ 与堆顶（最小值）pq.top()。
     • 如果 $S > pq.top()`：
       • 淘汰堆顶：sum -= pq.top(), pq.pop()
       • 新人入伙：sum += S, pq.push(S)
     • 否则：$S$ 不够格，忽略。
4. 对于 Type 2：直接输出 sum。

3. 复杂度分析

• 堆的插入和删除操作复杂度均为 $O(\log K)$。
• 查询操作复杂度 $O(1)$。
• 总时间复杂度：$O(N \log K)$。
• 对于 $N=2 \times 10^5$，计算量约为 $3 \times 10^6$，完全满足 1 秒时限。

参考代码 (C++14)

/**
 * 题目：金榜题名 (The Gold List)
 * 难度：GESP 6级
 * 算法：优先队列 / 小根堆 (Min-Heap)
 */

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

int main() {
    fast_io();

    int N, K;
    if (!(cin >> N >> K)) return 0;

    // 定义小根堆
    // 参数1: 元素类型 int
    // 参数2: 底层容器 vector<int>
    // 参数3: 比较函数 greater<int> (使其成为小根堆，越小越在上面)
    priority_queue<int, vector<int>, greater<int>> pq;

    // 记录当前堆中元素的总和，用 long long 防止溢出
    long long current_sum = 0;

    while (N--) {
        int type;
        cin >> type;

        if (type == 1) {
            int score;
            cin >> score;

            if (pq.size() < K) {
                // 如果没满，直接进
                pq.push(score);
                current_sum += score;
            } else {
                // 如果满了，看能不能挤掉最差的（堆顶）
                if (score > pq.top()) {
                    current_sum -= pq.top(); // 减去旧的
                    pq.pop();                // 移除旧的
                    
                    pq.push(score);          // 加入新的
                    current_sum += score;    // 加上新的
                }
                // 如果 score <= pq.top()，直接忽略
            }
        } else {
            // 询问
            cout << current_sum << "\n";
        }
    }

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstdlib>
#include <ctime>
#include <string>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
void solve(int N, int K, const vector<pair<int, int>>& ops, ofstream& fout) {
    priority_queue<int, vector<int>, greater<int>> pq;
    long long sum = 0;

    for (const auto& op : ops) {
        if (op.first == 1) {
            int s = op.second;
            if (pq.size() < K) {
                pq.push(s);
                sum += s;
            } else {
                if (s > pq.top()) {
                    sum -= pq.top();
                    pq.pop();
                    pq.push(s);
                    sum += s;
                }
            }
        } else {
            fout << sum << "\n";
        }
    }
}

// 辅助函数
int randRange(int min, int max) {
    if (min > max) return min;
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, K;
        vector<pair<int, int>> ops;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N=6; K=3;
            ops={{1,10}, {1,20}, {2,0}, {1,5}, {1,30}, {2,0}};
        }
        else if (i == 2) {
            // 样例2
            N=7; K=2;
            ops={{1,100}, {1,100}, {1,50}, {2,0}, {1,200}, {1,150}, {2,0}};
        }
        else if (i == 3) {
            // 只有查询，没有插入 (和为0)
            N = 10; K = 5;
            for(int j=0; j<N; j++) ops.push_back({2, 0});
        }
        else if (i == 4) {
            // 只有插入，最后一次查询 (K=1, 最大值)
            N = 100; K = 1;
            for(int j=0; j<N-1; j++) ops.push_back({1, randRange(1, 1000)});
            ops.push_back({2, 0});
        }
        else if (i == 5) {
            // 递增序列插入 (频繁替换)
            N = 1000; K = 10;
            for(int j=0; j<N; j++) {
                if (j % 10 == 0) ops.push_back({2, 0});
                else ops.push_back({1, j * 10});
            }
        }
        else if (i == 6) {
            // 递减序列插入 (只有前K个进，后面都不进)
            N = 1000; K = 10;
            for(int j=0; j<N; j++) {
                if (j % 10 == 0) ops.push_back({2, 0});
                else ops.push_back({1, 10000 - j});
            }
        }
        else {
            // 大规模随机 (N=2*10^5)
            N = 200000;
            if (i == 7) K = 1; // 极小K
            else if (i == 8) K = N; // 极大K (所有数都进)
            else K = 5000; // 中等K

            for(int j=0; j<N; j++) {
                // 30% 概率查询，70% 概率插入
                if (randRange(1, 10) <= 3) ops.push_back({2, 0});
                else ops.push_back({1, randRange(1, 1000000000)});
            }
        }

        // 写入输入
        fin << N << " " << K << "\n";
        for(const auto& op : ops) {
            if (op.first == 1) fin << "1 " << op.second << "\n";
            else fin << "2\n";
        }

        // 写入输出
        solve(N, K, ops, fout);

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}