小红闯关

贪心 + 最大堆

由题可知，每闯过k个关卡，就能获得一个跳关道具。

因此，下标为k的倍数的关卡都能获得一个跳关道具。

• [k, n-1]范围内，我们可以对其中的任何一个关卡使用跳关道具。
• [2k, n-1]范围内，我们可以对其中的任何一个关卡使用跳关道具。
• ...
• [jk, n-1]范围内，我们可以对其中的任何一个关卡使用跳关道具。

我们发现，这些范围有些部分是重叠的。对于重叠的部分，我们优先使用范围较小的跳关道具。

[jk, n-1]排除里面的最大值，然后[j-1k, n-1]就能够在剩余的范围内排除第二大的值。如果先使用[j-1k, n-1]排除了最大值，如果恰好第二大值在[j-1k, jk)这个范围内，[jk,n-1]的道具就白白浪费了，它只能排除[jk,n-1]中的最大值，该值在[j-1k,n-1]中可能第三大甚至第四大。

因此，为了充分利用跳关道具，我们需要先使用范围较小的跳关道具。

因此，我们从右往左遍历，当下标是k的倍数时，说明遇到了跳关道具，此时跳关时间加上之前遍历的元素的最大值。

然后继续遍历，遇到跳关道具，跳关时间就加上剩余元素的最大值。

最大值可以使用最大堆来进行记录。

代码实现如下：

import sys
import heapq

line = sys.stdin.readline().strip()
a = line.split()

n = int(a[0])
k = int(a[1])

line = sys.stdin.readline().strip()

nums = [int(num) for num in line.split()]

maxHeap = []
i = n - 1
maxJumpTime = 0
for i in range(n-1, -1, -1):     
    heapq.heappush(maxHeap, -nums[i])
    if i != 0 and i % k == 0:
        maxJumpTime += -heapq.heappop(maxHeap)
print(sum(nums) - maxJumpTime)

import java.util.*;

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

        int[] times = new int[n];
        for (int i = 0; i < n; i++) {
            times[i] = scanner.nextInt();
        }

        // 计算能获得的跳关道具数量
        int props = n / k;

        // 如果没有道具，直接返回所有关卡时间总和
        if (props == 0) {
            long sum = 0;
            for (int time : times) {
                sum += time;
            }
            System.out.println(sum);
            return;
        }

        // 使用小顶堆来保存我们要跳过的最大时间关卡
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        long totalSum = 0;

        for (int i = 0; i < n; i++) {
            totalSum += times[i];

            // 记录当前已获得的道具数量 (到第i+1关为止)
            int currentProps = i / k;

            // 如果当前已获得的道具数量多于堆的大小，说明刚获得了新道具
            if (currentProps > minHeap.size()) {
                minHeap.add(times[i]);
            }
            // 如果已经获得了道具，且当前关卡时间比堆中最小的要大，则替换
            else if (currentProps > 0 && times[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.add(times[i]);
            }
        }

        // 计算需要减去的总时间（被跳过的关卡）
        long skipSum = 0;
        while (!minHeap.isEmpty()) {
            skipSum += minHeap.poll();
        }

        System.out.println(totalSum - skipSum);
    }
}

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0;i < n;i ++ ) a[i] = sc.nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        long sum = 0;
        for(int i = n - 1;i >= k;i -- ) {
            pq.add(a[i]);
            sum += a[i];
            if(i % k == 0) {
                sum -= pq.poll();
            }
        }
        for(int i = k - 1;i >= 0;i -- ) sum += a[i];
        System.out.println(sum);
    }
}

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
int main() {
    LL n,k;
    cin>>n>>k;
    vector<LL>a(n);
    LL res=0;
    priority_queue<LL,vector<LL>,less<>>pq;
    for(int i=0;i<n;i++){
        cin>>a[i];
        res+=a[i];
    }
    for(int i=n-1;i>=0;i--){
        pq.push(a[i]);
        if(i!=0 && i%k ==0){
            int mx = pq.top();pq.pop();
            res -= mx;
        }
    }
    cout<<res;
}
// 64 位输出请用 printf("%lld")

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int cmp(const void*a,const void*b){
    return *(int*)a-*(int *)b;
}

int main() {
    int a, b;
    cin >> a >> b;
    vector<int> arr;
    int tmp = a;
    while (tmp--) { // 注意 while 处理多个 case
        int yl;
        scanf("%d", &yl);
        arr.push_back(yl);
    }
    if(b==1){
        printf("%d",arr[0]);
        return 0;
    }
    long long sum = 0;
    for (int i = 0; i < b; ++i) {
        sum += arr[i];
    }
    int left = a - a % b;
    int right = a;
    priority_queue<int> queue1;
    for(int i=left;i<right;++i){
        queue1.push(arr[i]);
    }
    if(!queue1.empty())
        queue1.pop();
    right = left;
    left = right -b;
    while(left>0){
        for(int i=left;i<right;++i){
            queue1.push(arr[i]);
        }
        queue1.pop();
        right = left;
        left = right -b;
    }
    while(!queue1.empty()){
        sum += queue1.top();
        queue1.pop();
    }
    printf("%lld", sum);
}

import sys

for line in sys.stdin:
    a = line.split()
    n, k = int(a[0]), int(a[1])
    num = list(map(int, input().split()))
    jump = n // k  # 有多少次跳的机会
    chance = [1] * (jump + 1)

    # 为每个元素添加索引信息，形成 (index, value) 元组
    num_with_index = [(i, v) for i, v in enumerate(num)]
    # 按照值从大到小排序
    maxnum = sorted(num_with_index, key=lambda x: x[1], reverse=True)

    jian = 0
    for i, x in maxnum:
        j = i // k  # 看在第几次能 jump
        for p in range(j, 0, -1):
            if chance[p] == 1:
                chance[p] = 0
                jump -= 1
                jian += x
                break
        if jump == 0:
            break      print(sum([x[1] for x in maxnum]) - jian)