Overview

A problem where you select exactly \(K\) out of \(N\) devices to put into energy-saving mode, minimizing the total power consumption.

Analysis

In this problem, we need to determine which devices to put into energy-saving mode to minimize the total power consumption.

First, when a device has power consumption \(A_i\), putting it into energy-saving mode reduces it to \(\lfloor A_i / 2 \rfloor\). In other words, the amount of power saved by that device is
$\( \text{savings}_i = A_i - \left\lfloor \frac{A_i}{2} \right\rfloor \)\( Therefore, by selecting the \)K$ devices with the largest savings and putting them into energy-saving mode, we can most effectively reduce the total power consumption.

For example, consider 3 devices with power consumption [10, 8, 6] and \(K=2\). - The savings for each device are [5, 4, 3]. - So, by selecting the first two (those with the largest savings) for energy-saving mode, the total becomes
\((10 + 8 + 6) - (5 + 4) = 24 - 9 = 15\), which is optimal.

In this way, the optimal strategy is to select the \(K\) devices with the largest savings.

A naive approach of searching for the element with the maximum savings each time would take \(O(NK)\) time, which exceeds the time limit when \(N\) or \(K\) is large. To efficiently repeat the operation of “extracting the maximum element,” we use a priority queue (heap).

Since Python’s heapq is a min-heap, we store values with their signs negated to use it as a max-heap.

Algorithm

1. For each device, compute the savings when put into energy-saving mode: \(\text{savings}_i = A_i - \lfloor A_i / 2 \rfloor\).
2. Compute the total power consumption assuming all devices are in normal mode: \(\text{total} = \sum_{i=1}^{N} A_i\).
3. Store the savings in a max-heap (a min-heap with negated signs).
4. Extract the top \(K\) savings and subtract them from \(\text{total}\).
5. Output the final \(\text{total}\).

Complexity

• Time complexity: \(O(N \log N)\)
  (\(O(N)\) for computing savings, \(O(N)\) for heap construction, \(O(K \log N)\) for \(K\) extractions)
• Space complexity: \(O(N)\)
  (list and heap for storing savings)

Implementation Notes

• Since Python’s heapq is a min-heap, when using it as a max-heap, store values with their signs negated.

• Input is read using sys.stdin.read for faster I/O.

• The key point is to compute the total sum and savings separately, then apply the difference at the end.

  Source Code

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))
    
    # 各機器の省エネ効果（どれだけ電力が減るか）を計算
    savings = []
    for a in A:
        original = a
        saved = a - (a // 2)
        savings.append(saved)
    
    # 総和の初期値（すべての機器が通常モード）
    total = sum(A)
    
    # 省エネ効果が大きい順にK個選ぶために、最大ヒープを使う
    # heapqは最小ヒープなので、符号を反転させて使う
    heap = [-s for s in savings]
    heapq.heapify(heap)
    
    # 効果の大きい上位K個を選ぶ
    for _ in range(K):
        max_saving = -heapq.heappop(heap)
        total -= max_saving
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.