Overview

This problem asks which devices to select when performing exactly \(K\) operations that “halve (round down)” each device’s power consumption, in order to minimize the total power consumption.

Analysis

The power consumption of each device \(i\) changes as \(A_i \rightarrow \lfloor A_i/2 \rfloor\) when the operation is applied.
The key insight is to consider how much the total decreases (the reduction amount).

The reduction amount for device \(i\) is [ A_i - \lfloor A_i/2 \rfloor ] Here, by properties of integers, [ A_i - \lfloor A_i/2 \rfloor = \lceil A_i/2 \rceil ] holds (if even, it decreases by \(A_i/2\); if odd, it decreases by \((A_i+1)/2\)).

In other words, the optimal strategy for “which devices to set to energy-saving mode” is to select the \(K\) devices with the largest reduction amounts.
This is because each device’s operation is independent of the others, and the total decrease equals the “sum of the selected reduction amounts,” so gathering the \(K\) largest reduction amounts minimizes the total.

Why a naive approach is difficult

• “Which \(K\) devices to select” is a combinatorial problem, and exhaustive search would require \(\binom{N}{K}\) combinations, which is far too many when \(N \le 2 \times 10^5\).
• Instead of comparing the values after the operation, comparing only the reduction amounts (benefits) makes the problem much simpler.

Concrete example

When \(A = [5, 4, 1]\): - \(5 \rightarrow 2\) gives a reduction of \(3\) (\(\lceil 5/2 \rceil = 3\)) - \(4 \rightarrow 2\) gives a reduction of \(2\) - \(1 \rightarrow 0\) gives a reduction of \(1\)

If \(K=2\), selecting the largest reductions \(3, 2\) is optimal, and the total becomes [ (5+4+1) - (3+2) = 10 - 5 = 5 ]

Algorithm

1. Compute the initial total \(total = \sum A_i\).
2. For each \(A_i\), compute the reduction amount \(r_i = \lceil A_i/2 \rceil\).
   Using only integers: [ \lceil A_i/2 \rceil = \left\lfloor \frac{A_i+1}{2} \right\rfloor ] So in Python, this can be computed as (a + 1) // 2.
3. Sort the reduction array in descending order and subtract the sum of the top \(K\) values: [ total - \sum{j=1}^{K} r{(j)} ] (where \(r_{(j)}\) is the \(j\)-th value when reduction amounts are sorted in descending order)

This way, “maximizing the reducible amount” = “minimizing the total after operations.”

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting the reduction amounts)
• Space complexity: \(O(N)\) (for storing the reduction amount array)

Implementation Notes

• The reduction amount can also be computed as a - (a//2), but using (a + 1) // 2 (corresponding to ceil(a/2)) in the code makes the intent clearer.

• Since it is “exactly \(K\) devices,” we must select exactly the top \(K\) reduction amounts (note that it is not “at most \(K\)” or “fewer than \(K\)”).

• Since \(N\) can be large, using sys.stdin.readline for input is recommended to be safe.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    total = sum(A)
    reductions = [(a + 1) // 2 for a in A]  # a - floor(a/2) = ceil(a/2)
    reductions.sort(reverse=True)
    total -= sum(reductions[:K])
    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.