Overview

This is a problem where you select exactly \(K\) devices out of \(N\) devices to set to energy-saving mode (which halves power consumption, rounded down), and minimize the total power consumption of all devices.

Analysis

Key Insight: Focus on the Reduction Amount

When setting energy-saving mode, the power consumption changes from \(A_i\) to \(\lfloor A_i / 2 \rfloor\).

At this time, the amount of power reduced is: $\(A_i - \lfloor A_i / 2 \rfloor = \lceil A_i / 2 \rceil = \frac{A_i + 1}{2}\)$

For example: - When \(A_i = 10\): reduction amount \(= 10 - 5 = 5\) - When \(A_i = 7\): reduction amount \(= 7 - 3 = 4\) - When \(A_i = 1\): reduction amount \(= 1 - 0 = 1\)

Greedy Approach is Optimal

Since we want to minimize the total power consumption, we should prioritize setting energy-saving mode on devices with larger reduction amounts.

This is intuitively obvious. For example, if we’re selecting \(K=2\) devices from 5 devices with reduction amounts \([5, 4, 3, 2, 1]\), choosing the devices with reduction amounts \(5\) and \(4\) reduces the total the most.

Why is the Greedy Approach Correct?

• Whether to set energy-saving mode on each device is an independent choice
• Energy-saving mode can be set at most once per device
• Choosing any device has no effect on other devices

In such situations, simply selecting the \(K\) devices with the largest reduction amounts gives the optimal solution.

Algorithm

1. Calculate the reduction amount \(A_i - \lfloor A_i / 2 \rfloor\) for each device
2. Select the \(K\) devices with the largest reduction amounts
3. Subtract the total reduction amount of the selected \(K\) devices from the original total power consumption

Concrete Example

For \(N = 4, K = 2, A = [10, 7, 3, 1]\):

Device	Power Consumption \(A_i\)	After Energy-Saving	Reduction Amount
1	10	5	5
2	7	3	4
3	3	1	2
4	1	0	1

Selecting 2 devices in order of largest reduction amounts: Device 1 and Device 2 (reduction amount \(5 + 4 = 9\))

Answer: \(10 + 7 + 3 + 1 - 9 = 12\)

Complexity

• Time Complexity: \(O(N \log K)\)
  • Calculating reduction amounts: \(O(N)\)
  • Selecting top \(K\) items (heapq.nlargest): \(O(N \log K)\)
• Space Complexity: \(O(N)\)
  • Array to store reduction amounts

Implementation Notes

1. Calculating the Reduction Amount

   reduction = a - a // 2  # This is the same as (a + 1) // 2
   

   Python’s // is floor division, so it correctly calculates \(\lfloor A_i / 2 \rfloor\).

2. Efficiently Getting the Top K Items

   heapq.nlargest(K, reductions)
   

   Using heapq.nlargest is more efficient than sorting the entire array to get the top \(K\) items (especially when \(K\) is much smaller than \(N\)).

3. No Worry About Integer Overflow Python supports arbitrary precision integers, so there’s no worry about overflow even when \(A_i \leq 10^9\) and the total becomes large.

Source Code

import heapq

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # When setting energy-saving mode, power consumption changes from A_i to floor(A_i / 2)
    # Reduction amount is A_i - floor(A_i / 2) = ceil(A_i / 2) = (A_i + 1) // 2
    # To minimize the total, set energy-saving mode on devices with larger reduction amounts
    
    # Calculate reduction amounts
    reductions = []
    for a in A:
        reduction = a - a // 2  # = (a + 1) // 2
        reductions.append(reduction)
    
    # Select K devices in order of largest reduction amounts
    # Use heapq to find the top K reduction amounts
    largest_reductions = heapq.nlargest(K, reductions)
    
    total = sum(A)
    total -= sum(largest_reductions)
    
    print(total)

solve()

---

This editorial was generated by claude4.5opus.