\(N\) 台のスマートフォンは、現在のバッテリー残量に基づいて、「既に電池切れ」「充電しないと電池切れ」「充電しなくても大丈夫」の3種類のグループに分けられます。

このうち最初の1,3番目のグループのものは充電しようがしまいが結果に変化はありません。2つ目のグループのものを充電すると、最終的に使えるスマートフォンが1台増えます。よって、充電器は可能限りこのグループに割り当てるのが最適です。

以上より3つのグループに属するスマートフォンの数をそれぞれ \(P,Q,R\) とすると、求める答えは \(R+\min(K,Q)\) となります。

実装例 (C++)

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

int main(){
  int n, l, k, y;
  cin >> n >> l >> k >> y;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  int q = 0, r = 0;
  for(int i=0; i<n; i++){
    if(l < a[i] && a[i] <= l + y){
      q++;
    }else if(l + y < a[i]){
      r++;
    }
  }
  cout << r + min(k, q) << endl;
}

実装例 (Python)

N, L, K, Y = map(int, input().split())
A = list(map(int, input().split()))
Q, R = 0, 0
for a in A:
  if L < a <= L+Y:
    Q += 1
  elif L+Y < a:
    R += 1

print(R + min(K, Q))