İnək Akademiyası I (Həll təhlili)

Verilmiş ədədlər massivi üçün $h$-indeksin necə müəyyən ediləcəyini nəzərdən keçirək. Əvvəlcə massivi azalan sırada düzəldək. Sonra elə ən böyük $h$ dəyərini tapaq ki, $1$-dən $h$-a qədər olan mövqelərdəki elementlər $h$-dan kiçik olmasın. Başqa sözlə, a_h \ge h şərtini ödəyən maksimal $h$-ı axtarırıq.

Məsələn, aşağıdakı halda $h$-indeks $3$-ə bərabərdir, çünki a_3 \ge 3, lakin a_4 < 4.

$l$ sitatı əlavə etdikdən sonra $h$-indeks $1$-dən çox arta bilməz. Həqiqətən, a_{h+1} < h + 1 olduğundan və hər məqaləyə ən çoxu bir dəfə istinad etmək mümkün olduğundan, edə biləcəyimiz maksimum şey a_{h + 1}-i $1$ artırmaqdır (əgər əvvəlcədən a_{h + 1} = h olarsa).

Sonra h + 1 mövqeyindən başlayaraq daha kiçik indekslər istiqamətində hərəkət edərək massivin elementlərini $1$ artıracağıq. Başqa sözlə, a[\max(1, h - l + 2); h + 1] parçasındakı elementləri $1$ artıracağıq.

Bundan sonra massivi yenidən azalan sıraya görə düzəldib $h$-indeksi yenidən hesablayacağıq. Alınan dəyər cavab olacaq.

Nümunə

Birinci nümunədə Bessi öz məqalələrinə istinad edə bilmir, buna görə də (1, 100, 2, 3) dəsti üçün onun $h$-indeksi $2$-yə bərabərdir.

İkinci nümunədə, əgər Bessi üçüncü məqaləyə istinad edərsə, sitatların sayı (1, 100, 3, 3) olar. Bu halda $h$-indeks $3$-ə qədər artacaq.

Aşağıdakı nümunəni nəzərdən keçirək. Ədədlər artıq azalan sırada verilmişdir. Bu massivin $h$-indeksi $4$-ə bərabərdir.

• Tutaq ki, l = 2. $a[4;5]$ elementlərini $1$ artırıb massivi yenidən azalan sıraya görə düzəldək. Alınan massivin $h$-indeksi yenə də $4$-ə bərabər olacaq.

• Tutaq ki, l = 4. $a[2;5]$ elementlərini $1$ artırıb massivi azalan sıraya görə düzəldək. Nəticədə alınan massivin $h$-indeksi $5$-ə bərabər olacaq.

Alqoritmin reallaşdırılması

hIndex funksiyası əvvəlcədən azalan sıraya görə düzədilmiş massiv üçün $h$-indeksi hesablayır. İndeksləmə $1$-dən başlayır. Funksiya v_i \ge i şərtini ödəyən maksimal $i$ dəyərini qaytarır. Əgər belə indeks yoxdursa ($h$-indeks massivinin $n$-ə bərabər olduğu hal), onda $n$-ə bərabər olan v.size() - 1 dəyərini qaytarırıq.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Massivi birinci elementdən başlayaraq azalan sıraya görə düzəldirik.

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

İlkin massivin $h$-indeksini hesablayırıq.

h = hIndex(v);

h + 1 mövqeyindən başlayaraq daha kiçik indekslər istiqamətində hərəkət edərək müvafiq v_i dəyərlərini $1$ artırırıq.

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

Massivi azalan sıraya görə düzəldib onun yeni $h$-indeksini hesablayırıq.

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

Cavabı çap edirik.

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