题目链接

小苯的比赛上分

题目描述

小苯有 个账号，初始分数分别为 。

他将进行 场比赛。根据名言“只要你永远使用分数最低的账号参赛，那么你的 max_score 将单调不降”，小苯在每场比赛前，都会选择当前所有账号中分数最低的一个去参赛。

第 场比赛会使参赛账号分数增加 。

我们需要计算并输出每场比赛结束后，小苯所有账号中的最高分是多少。

解题思路

这是一个动态模拟问题。我们需要维护一组不断变化的数据（账号分数），并高效地执行以下操作：

  1. 找到当前的最小值。
  2. 更新这个最小值（加上比赛得分）。
  3. 找到更新后的全局最大值。

由于比赛场次 和账号数量 都可能很大，简单的数组遍历（每场比赛都 查找最小值和最大值）会导致 的总时间复杂度，这会超时。

高效的数据结构：优先队列 (最小堆)

为了快速找到最小值，优先队列（最小堆） 是一个理想的数据结构。它可以让我们在 的时间内获取并移除最小值。

同时，我们还需要跟踪全局的最大值。一个简单的最小堆无法直接提供最大值信息。不过，我们可以用一个额外的变量 max_score 来实时维护它。

算法步骤

  1. 初始化：

    • 创建一个最小堆，并将所有 个账号的初始分数都加入堆中。
    • 创建一个变量 max_score，并在将分数入堆的同时，遍历找到初始的最高分并存入该变量。

  2. 模拟 场比赛：

    • 对于每一场比赛，从比赛增分数组中取出当前的增分值 。
    • 从最小堆的堆顶取出（并移除）当前分数最低的账号的分数 min_val。
    • 计算该账号参赛后的新分数 new_val = min_val + w_i。
    • 将 new_val 重新插入到最小堆中。
    • 更新全局最高分：max_score = max(max_score, new_val)。因为只有新分数可能成为新的最高分，所以只需将它与当前的 max_score 比较即可。
    • 输出当前的 max_score。

这个方法将每次操作的时间复杂度从 优化到了 ，足以应对本题的数据范围。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long max_score = -1;

    for (int i = 0; i < n; ++i) {
        long long score;
        cin >> score;
        pq.push(score);
        if (score > max_score) {
            max_score = score;
        }
    }

    for (int i = 0; i < m; ++i) {
        long long increase;
        cin >> increase;

        long long min_val = pq.top();
        pq.pop();

        long long new_val = min_val + increase;
        pq.push(new_val);

        if (new_val > max_score) {
            max_score = new_val;
        }

        cout << max_score << endl;
    }

    return 0;
}

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        PriorityQueue<Long> pq = new PriorityQueue<>();
        long maxScore = -1;

        for (int i = 0; i < n; i++) {
            long score = sc.nextLong();
            pq.add(score);
            if (score > maxScore) {
                maxScore = score;
            }
        }

        for (int i = 0; i < m; i++) {
            long increase = sc.nextLong();

            long minVal = pq.poll();
            long newVal = minVal + increase;
            pq.add(newVal);

            if (newVal > maxScore) {
                maxScore = newVal;
            }

            System.out.println(maxScore);
        }
    }
}

import sys
import heapq

def solve():
    n, m = map(int, sys.stdin.readline().split())
    
    initial_scores = list(map(int, sys.stdin.readline().split()))
    increases = list(map(int, sys.stdin.readline().split()))
    
    min_heap = []
    max_score = -1
    
    for score in initial_scores:
        heapq.heappush(min_heap, score)
        if score > max_score:
            max_score = score
            
    for increase in increases:
        min_val = heapq.heappop(min_heap)
        
        new_val = min_val + increase
        heapq.heappush(min_heap, new_val)
        
        if new_val > max_score:
            max_score = new_val
            
        print(max_score)

solve()

算法及复杂度

  • 算法：模拟 + 优先队列（最小堆）

  • 时间复杂度: 。初始化建堆和寻找最大值需要 。之后进行 场比赛，每场比赛涉及一次出堆和一次入堆，时间复杂度均为 ，所以模拟部分总共是 。

  • 空间复杂度: ，用于存储优先队列中的 个账号分数。