Коров'яча академія I#11231

Коров'яча академія I (Розбір)

Розглянемо, як визначити $h$ -індекс для заданого масиву чисел. Спочатку відсортуємо масив за спаданням. Потім знайдемо найбільше значення $h$ таке, що елементи на позиціях від $1$ до $h$ мають значення не менші за $h$ . Іншими словами, шукаємо максимальне $h$ , для якого виконується умова $a_{h} \geq h$ a_h \ge h.

Наприклад, у наступному випадку $h$ -індекс дорівнює $3$ , оскільки $a_{3} \geq 3$ a_3 ≥ 3, але $a_{4} < 4$ a_4 < 4.

Після додавання $l$ цитувань $h$ -індекс не може збільшитися більш ніж на $1$ . Справді, оскільки $a_{h + 1} < h + 1$ a_{h+1} < h + 1, а кожну статтю можна процитувати не більше одного разу, максимум, що ми можемо зробити, – це збільшити $a_{h + 1}$ a_{h + 1} на $1$ (якщо початково $a_{h + 1} = h$ a_{h + 1} = h).

Далі, починаючи з позиції $h + 1$ h + 1 і рухаючись у бік менших індексів, будемо збільшувати елементи масиву на $1$ . Іншими словами, збільшимо на $1$ елементи на відрізку $a [ma x (1, h - l + 2); h + 1]$ a[max(1, h - l + 2); h + 1].

Після цього знову відсортуємо масив за спаданням і перерахуємо $h$ -індекс. Отримане значення і буде відповіддю.

Приклад

У першому прикладі Бессі не може цитувати свої статті, тому її $h$ -індекс для набору $(1, 100, 2, 3)$ (1, 100, 2, 3) дорівнює $2$ .

У другому прикладі, якщо Бессі процитує третю статтю, кількість цитувань стане $(1, 100, 3, 3)$ (1, 100, 3, 3). У цьому випадку $h$ -індекс збільшиться до $3$ .

Розглянемо наступний приклад. Числа вже наведені в порядку спадання. $h$ -індекс даного масиву дорівнює $4$ .

Нехай $l = 2$ l = 2. Збільшимо елементи $a [4; 5]$ на $1$ і знову відсортуємо масив за спаданням. $h$ -індекс отриманого масиву як і раніше дорівнює $4$ .

Нехай $l = 4$ l = 4. Збільшимо елементи $a [2; 5]$ на $1$ і потім відсортуємо масив за спаданням. У результаті $h$ -індекс отриманого масиву стане рівним $5$ .

Реалізація алгоритму

Функція hIndex обчислює $h$ -індекс для масиву, попередньо відсортованого за спаданням. Індексація починається з $1$ . Функція повертає максимальне значення $i$ , для якого виконується умова $v_{i} \geq i$ v_i \ge i. Якщо такого індексу немає ( $h$ -індекс масиву дорівнює $n$ ), то повертаємо значення $v . s i z e () - 1$ v.size() - 1, рівне $n$ .

int hIndex(vector<int> &v)
{
  for (int i = 1; i < v.size(); i++)
    if (v[i] < i) return i - 1;
  return v.size() - 1;
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d", &n, &l);
v.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &v[i]);

Сортуємо масив за спаданням, починаючи з першого елемента.

sort(v.begin() + 1, v.end(), greater<int>());

Обчислюємо $h$ -індекс вихідного масиву.

h = hIndex(v);

Починаючи з позиції $h + 1$ h + 1 і рухаючись у бік менших індексів, збільшуємо відповідні значення $v_{i}$ v_i на $1$ .

for (i = h + 1; i > max(h - l + 1, 0); i--)
  v[i]++;

Сортуємо масив за спаданням і обчислюємо його новий $h$ -індекс.

sort(v.begin() + 1, v.end(), greater<int>());
h = hIndex(v);

Виводимо відповідь.

printf("%d\n", h);