题解 | 小红闯关

/*
我的想法是从最后一个获得道具的位置开始向前，看在每一个位置上获得的道具最多可以减少多少时间，因为后面关卡的道具不能用在获得结点之前，所以说要从最后一个获得道具的位置进行判断，去掉跳过的关卡的前提下进行前面获得道具最大跳过时间的判断

具体的思路是1、计算出不用跳关的总用时sum，并设置变量save_time
        2、首先维护一个大顶堆，初始为空，然后从后向前扫描数组，每次扫描时先检测是否获得道具，即为(i + 1)/k == 0，若获得道具则使得 save_time + 大顶堆堆顶的值，并把堆顶移除，扫描后将关卡加入大顶堆
        3、扫描结束后得到save_time，用sum - save_time即可得到所需的最小时间
*/
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100000000

/*手动实现一个大顶堆*/

//定义大顶堆结构体
struct maxheap{
   long long heap[MaxSize];
   int size;
};

//1、定义初始化函数
void Init(struct maxheap *h){
    h->size = 0;
}

//2、交换元素值
void swap(long long *a, long long *b){
    long long tmp = *a;
    *a = *b;
    *b = tmp;
}


//3、实现下沉操作
void sink(struct maxheap *h, int i){
    while(1){
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if(left < h->size && h->heap[left] > h->heap[largest]){
            largest = left;
        }
        if(right < h->size && h->heap[right] > h->heap[largest]){
            largest = right;
        }
        if(largest == i){
            break;
        }
        else{
            swap(&h->heap[i],&h->heap[largest]);
            i = largest;
        }
    }
}

//4、实现上浮操作
void Float(struct maxheap *h, int i){
    while(i >= 0){
        int parent = (i - 1) / 2;
        if(h->heap[i] <= h->heap[parent]){
            break;
        }
        else{
            swap(&h->heap[i], &h->heap[parent]);
            i = parent;
        }
    }
}

//5、插入操作
void push(struct maxheap *h, long long n){
    if(h->size >= MaxSize){
        return;
    }
    else{
        h->heap[h->size] = n;
        Float(h, h->size);
        h->size ++;
    }
}

//6、弹出操作
int pop(struct maxheap *h, long long *n){
    if(h->size <= 0){
        return 0;
    }
    else{
        *n = h->heap[0];
        swap(&h->heap[h->size - 1],&h->heap[0]);
        h->size--;
        sink(h, 0);
        return 1;
    }
}

//取堆顶元素
long long Top(struct maxheap h){
    if(h.size <= 0){
        return -1;
    }
    else{
        return h.heap[0];
    }
}


//主函数
int main() {
    //读取数据
    long long n, k;
    scanf("%lld %lld\n", &n, &k);
    long long *a = (long long *)malloc(sizeof(long long) * n);
    if(a == NULL){
        printf("Failed Malloc!\n");
        return -1;
    }
    long long sum = 0;//res记录最终的结果，初始化为0
    for(long long i = 0; i < n; i++){
        scanf("%lld", a + i);
        sum += *(a + i);//res先取所有关卡的时间和
    }
    
    long long save_time = 0;//节省的时间

    //建立大顶堆
    struct maxheap h;
    Init(&h);

    //从最后一个元素开始遍历数组
    for(int i = n - 1; i >= 0; i--){
       if((i + 1) % k == 0){//是获得道具的关卡
          long long tmp;
          if(pop(&h, &tmp)){
            save_time += tmp;
          }
       }
       push(&h,a[i]);
    }
    printf("%lld\n",sum - save_time);//打印结果
    //释放空间
    free(a);
    return 0;
}