問題概要

$N$ 人の髪の長さは最初 $L_{1}, L_{2}, \dots, L_{N}$ であった。

各人の髪の長さは 1 日に 1 ずつ伸びる。

初めて髪の長さが $T$ 以上の人が $P$ 人以上となるのは何日後かを求めよ。

制約

$1 \le N, T, L_{i} \le 100$
$1 \le P \le N$

解法 (1)：シミュレーション

まず、最初の解法は単純にシミュレーションすることです。 $0, 1, 2, \dots$ 後について、髪の長さを 1 ずつ増やしていき、髪の長さが $T$ 以上である人数を数えていこう。

この人数が $P$ 人以上となった瞬間の日数を答えればよい。

コード

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

int main() {
    int N, T, P;
    cin >> N >> T >> P;
    vector<int> L(N);
    for (int i = 0; i < N; i++) cin >> L[i];

    for (int day = 0; day <= T; day++) {
        int num = 0;
        for (int i = 0; i < N; i++) {
            if (L[i] >= T) num++;
            L[i]++;
        }
        if (num >= P) {
            cout << day << endl;
            return 0;
        }
    }
}

解法 (2)：ソート

もう一つの解法は、初期状態の髪の長さが長い順に $P$ 人について、全員の髪の長さが $T$ 以上になるのが何日後であるかを求める方法だ。

具体的には

$L$ を大きい順にソートする
L[P-1] がはじめて T 以上となるまでの日数を答える

というようにすればよい。

コード

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

int main() {
    int N, T, P;
    cin >> N >> T >> P;
    vector<int> L(N);
    for (int i = 0; i < N; i++) cin >> L[i];

    sort(L.begin(), L.end(), greater<int>());
    cout << max(T - L[P-1], 0) << endl;
}