小苯的比赛上分

[题目链接](https://www.nowcoder.com/practice/f5c52183dfb148489321f881239216c1)

思路

小苯有 个账号，每次比赛都用当前分数最低的账号参赛，赛后该账号分数增加 。要求每场比赛结束后输出所有账号中的最高分。

关键观察

每次操作都是：取出最小值，加上一个增量，再放回去。这恰好是最小堆（优先队列）的经典操作。

算法流程

  1. 将所有初始分数放入最小堆，同时记录当前全局最大值 。
  2. 对每场比赛：

- 从堆顶弹出最小值 ；

- 令 ，然后放回堆中；

- 更新 ，输出 。

由于 （分数增加值为正），全局最大值只可能不降，所以只需维护一个变量 即可。

样例演示

初始分数 ，。

比赛 堆顶(最低分) 赛后分数
1 10 1145 1155 1600
2 400 1155 1555 1600
3 500 1222 1722 1722
4 1000 1500 2500 2500
5 2000 1538 3538 3538
6 10000 1555 11555 11555

复杂度

  • 时间复杂度：，建堆 ，每次操作一次弹出和一次插入各 ，共 次。
  • 空间复杂度：，堆的大小。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long mx = LLONG_MIN;
    for(int i = 0; i < n; i++){
        long long x;
        cin >> x;
        pq.push(x);
        mx = max(mx, x);
    }
    for(int i = 0; i < m; i++){
        long long d;
        cin >> d;
        long long lo = pq.top();
        pq.pop();
        lo += d;
        mx = max(mx, lo);
        pq.push(lo);
        cout << mx << "\n";
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        PriorityQueue<Long> pq = new PriorityQueue<>();
        long mx = Long.MIN_VALUE;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            long x = Long.parseLong(st.nextToken());
            pq.offer(x);
            mx = Math.max(mx, x);
        }
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            long d = Long.parseLong(st.nextToken());
            long lo = pq.poll();
            lo += d;
            mx = Math.max(mx, lo);
            pq.offer(lo);
            sb.append(mx).append('\n');
        }
        System.out.print(sb);
    }
}