Overview

This problem asks for the minimum number of turns to destroy \(N\) rocks. You can use at most \(K\) dynamites (each destroys a rock in 1 turn), and for the remaining rocks, you must use a hammer which takes turns equal to the rock’s hardness.

Analysis

Key Insight

First, let’s consider the number of turns required to destroy each rock.

• Using dynamite: 1 turn regardless of hardness
• Using hammer: \(H_i\) turns equal to the hardness \(H_i\)

Although rocks must be processed in order, you can freely choose which rocks to use dynamite on.

Optimal Strategy

Using dynamite allows you to destroy a rock that would normally take \(H_i\) turns in just 1 turn. In other words, you save \(H_i - 1\) turns.

To maximize savings, you should use dynamite on rocks with higher hardness!

For example, with \(H = [3, 10, 2, 8]\) and \(K = 2\): - Sorted by hardness in descending order: \(10, 8, 3, 2\) - Use dynamite on rocks with hardness \(10\) and \(8\) - Required turns = \(2\) (dynamite) \(+ 3 + 2\) (hammer) \(= 7\)

Formula Derivation

• Using \(K\) dynamites → \(K\) turns
• Remaining \(N - K\) rocks are destroyed with hammer → total turns equal to sum of remaining hardnesses

\[\text{Minimum turns} = K + (\text{sum of all hardnesses} - \text{sum of top } K \text{ hardnesses})\]

Algorithm

Let’s consider efficient methods to find the top \(K\) hardnesses.

Method 1: Sorting

Sort all elements and extract the top \(K\). Time complexity \(O(N \log N)\).

Method 2: Heap (This Solution)

Use a min-heap to maintain “the largest \(K\) elements seen so far” with constant size \(K\).

1. If the heap size is less than \(K\), add the element
2. If the size is \(K\) and the new element is larger than the heap’s minimum, remove the minimum and add the new element

This method finds the top \(K\) elements with just a single pass through the array.

Corner Cases

• When \(K \geq N\): Destroy all rocks with dynamite → answer is \(N\)
• When \(K = 0\): Destroy all with hammer → answer is \(\sum H_i\)

Complexity

• Time complexity: \(O(N \log K)\)
  • Each element requires at most one heap operation (\(O(\log K)\))
• Space complexity: \(O(K)\)
  • Maintains a heap of size \(K\)

Implementation Notes

1. Using heapq.heapreplace: Instead of doing heappop followed by heappush, using heapreplace is more efficient (only one heap operation).

2. Handling corner cases first: Processing cases where \(K \geq N\) or \(K = 0\) at the beginning keeps the main logic simple.

3. Python’s heapq is a min-heap: When you want to manage maximum values, one approach is to negate the signs, but in this problem, we directly utilize the min-heap by managing “the minimum among the top \(K\) elements”.

Source Code

import heapq

def solve():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    if K >= N:
        # Can destroy all rocks with dynamite
        print(N)
        return
    
    if K == 0:
        # Cannot use dynamite, must hammer all rocks
        print(sum(H))
        return
    
    # When using K dynamites, it's optimal to use them on the K rocks with highest hardness
    # Rocks using dynamite: 1 turn
    # Rocks destroyed with hammer: H_i turns
    
    # Use dynamite on K rocks with highest hardness, destroy the rest with hammer
    # Minimum turns = K + (sum of all hardnesses - sum of top K hardnesses)
    
    # Find the sum of top K hardnesses
    # Use heap for efficiency
    
    # Manage K maximum values with a min-heap
    min_heap = []
    
    for h in H:
        if len(min_heap) < K:
            heapq.heappush(min_heap, h)
        elif h > min_heap[0]:
            heapq.heapreplace(min_heap, h)
    
    top_k_sum = sum(min_heap)
    total_sum = sum(H)
    
    # Rocks using dynamite: K rocks × 1 turn = K turns
    # Rocks destroyed with hammer: (N-K) rocks, total hardness = total_sum - top_k_sum turns
    result = K + (total_sum - top_k_sum)
    print(result)

solve()

---

This editorial was generated by claude4.5opus.