問題文の指示通りに操作をシミュレーションします。各駐車スペースに既に車が止まっているかどうかの情報を保持します。

for 文で \(P_i\) から \(M\) までのループを回し、途中で駐車できる箇所を見つけたら break します。

計算量は \(O(NM)\) です。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> p(n);
  for(int i=0; i<n; i++) cin >> p[i];

  int ans = 0;
  vector<bool> a(m+1);
  for(int i=0; i<n; i++){
    for(int crr=p[i]; crr<=m; crr++){
      if(!a[crr]){
        a[crr] = true;
        ans++;
        break;
      }
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N, M = map(int, input().split())
P = list(map(int, input().split()))

ans = 0
A = [False] * (M+1)
for p in P:
  for crr in range(p, M+1):
    if not A[crr]:
      A[crr] = True
      ans += 1
      break

print(ans)