题解 | 小苯的比赛上分

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 定义最小堆结构
typedef struct {
    long long* data;  // 存储堆元素（用long long防溢出）
    int size;         // 当前堆大小
    int capacity;     // 堆容量
} MinHeap;

// 交换两个long long值
void swap(long long* a, long long* b) {
    long long temp = *a;
    *a = *b;
    *b = temp;
}

// 堆的下沉操作（维护最小堆性质）
void heapify(MinHeap* heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->data[left] < heap->data[smallest]) {
        smallest = left;
    }
    if (right < heap->size && heap->data[right] < heap->data[smallest]) {
        smallest = right;
    }

    if (smallest != idx) {
        swap(&heap->data[idx], &heap->data[smallest]);
        heapify(heap, smallest);
    }
}

// 初始化最小堆
MinHeap* initHeap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->data = (long long*)malloc(sizeof(long long) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

// 插入元素到堆
void pushHeap(MinHeap* heap, long long val) {
    if (heap->size >= heap->capacity) {
        // 扩容（按2倍扩容，适配1e5+1e5的最大规模）
        heap->capacity *= 2;
        heap->data = (long long*)realloc(heap->data,
                                         sizeof(long long) * heap->capacity);
    }

    // 插入到最后，然后上浮
    int idx = heap->size++;
    heap->data[idx] = val;
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (heap->data[parent] > heap->data[idx]) {
            swap(&heap->data[parent], &heap->data[idx]);
            idx = parent;
        } else {
            break;
        }
    }
}

// 弹出堆顶（最小值）
long long popHeap(MinHeap* heap) {
    if (heap->size == 0) {
        return -1; // 堆空，题目中不会出现
    }
    long long top = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    heapify(heap, 0);
    return top;
}

// 获取堆顶（最小值，不弹出）
long long peekHeap(MinHeap* heap) {
    return heap->size > 0 ? heap->data[0] : -1;
}

// 释放堆内存
void freeHeap(MinHeap* heap) {
    free(heap->data);
    free(heap);
}

int main() {

    int n, m;
    scanf("%d %d", &n, &m);

    // 初始化最小堆，初始容量设为n（后续自动扩容）
    MinHeap* heap = initHeap(n);
    long long currentMax = 0; // 维护当前最高分

    // 读取n个账号分数，初始化堆和当前最大值
    for (int i = 0; i < n; i++) {
        long long a;
        scanf("%lld", &a);
        pushHeap(heap, a);
        if (a > currentMax) {
            currentMax = a;
        }
    }

    // 处理m场比赛
    for (int i = 0; i < m; i++) {
        long long b;
        scanf("%lld", &b);

        // 弹出当前最低分
        long long minScore = popHeap(heap);
        // 计算新分数
        long long newScore = minScore + b;
        // 新分数入堆
        pushHeap(heap, newScore);

        // 更新当前最高分（仅当新分数更大时）
        if (newScore > currentMax) {
            currentMax = newScore;
        }

        // 输出当前最高分
        printf("%lld\n", currentMax);
    }

    // 释放内存
    freeHeap(heap);
    return 0;
}