省エネモードにすることで削減される消費電力はおよそ \(\frac{A_i}{2}\) であることから、消費電力が大きな機器から順に省エネモードにするのが最適です。よって、\(A\) をソートし、大きい方から \(K\) 個は \(2\) で割ってから、残りはそのまま合計したものが答えとなります。

ソートにより計算量は O\((N\log N)\) となります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  sort(a.begin(), a.end());

  long long ans=0;
  for(int i=0; i<n-k; i++) ans += a[i];
  for(int i=n-k; i<n; i++) ans += a[i] / 2;
  cout << ans << endl;
}

実装例 (Python)

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

ans = sum(A[:-K]) + sum(x//2 for x in A[-K:])
print(ans)