题目链接

小苯的比赛上分

题目描述

有一款著名的大型多人电子竞技游戏网站"喜爱福"，网站通常会举办一些比赛。通常一名参赛选手只有一个账号，但不难猜到，总会有人"开小号"上分。

小苯就是一位该游戏的忠实玩家，他总共有 个账号，每个账号的分数分别为 。他深谙游戏中一位著名玩家 st****lk 的一句名言："只要你永远打分更低的号，那么你的最高分就是单调不降"。

现在我们记录了小苯 次的比赛记录，已知小苯每次都会谨记 st****lk 的名言，从而使用分数最低的账号参赛。现在我们想知道小苯每次参赛后，他的最高分是多少。

输入:

  • 第一行两个正整数 ，分别表示小苯的账号个数和新参加的比赛记录数
  • 第二行 个整数 ，表示小苯每个账号目前的分数
  • 第三行 个整数 ，分别表示小苯每次比赛后，分数的变化值

输出:

  • 输出 行，每行一个整数，表示小苯参与完第 场比赛后，他的最高分的值

解题思路

这是一个模拟问题，可以通过以下步骤解决：

  1. 关键发现：

    • 每次都使用分数最低的账号参赛
    • 需要维护所有账号的分数
    • 每次比赛后需要更新最高分

  2. 模拟策略：

    • 使用优先队列（小根堆）维护所有账号分数
    • 每次从堆顶取出最小分数的账号
    • 更新该账号分数后重新入堆
    • 维护当前最高分

  3. 具体步骤：

    • 初始化优先队列和最高分
    • 对每场比赛：
      • 取出最小分数
      • 加上比赛分数变化
      • 更新最高分
      • 将新分数入堆

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    priority_queue<int, vector<int>, greater<int>> pq;  // 小根堆
    int max_score = 0;
    
    // 读入初始分数
    for(int i = 0; i < n; i++) {
        int score;
        cin >> score;
        pq.push(score);
        max_score = max(max_score, score);
    }
    
    // 处理每场比赛
    for(int i = 0; i < m; i++) {
        int delta;
        cin >> delta;
        
        int min_score = pq.top();  // 取出最小分数
        pq.pop();
        min_score += delta;  // 更新分数
        pq.push(min_score);
        
        max_score = max(max_score, min_score);  // 更新最高分
        cout << max_score << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();  // 小根堆
        int maxScore = 0;
        
        // 读入初始分数
        for(int i = 0; i < n; i++) {
            int score = sc.nextInt();
            pq.offer(score);
            maxScore = Math.max(maxScore, score);
        }
        
        // 处理每场比赛
        for(int i = 0; i < m; i++) {
            int delta = sc.nextInt();
            
            int minScore = pq.poll();  // 取出最小分数
            minScore += delta;  // 更新分数
            pq.offer(minScore);
            
            maxScore = Math.max(maxScore, minScore);  // 更新最高分
            System.out.println(maxScore);
        }
    }
}

import heapq

n, m = map(int, input().split())
scores = list(map(int, input().split()))
deltas = list(map(int, input().split()))

heapq.heapify(scores)  # 转换为小根堆
max_score = max(scores)  # 初始最高分

# 处理每场比赛
for delta in deltas:
    min_score = heapq.heappop(scores)  # 取出最小分数
    min_score += delta  # 更新分数
    heapq.heappush(scores, min_score)
    
    max_score = max(max_score, min_score)  # 更新最高分
    print(max_score)

算法及复杂度

  • 算法：优先队列（小根堆）
  • 时间复杂度： - 每场比赛需要一次堆操作
  • 空间复杂度： - 需要存储所有账号分数