LearnToCP
Prijavi se
Navigacija
PočetnaRoad-mapaProblemiO Nama
Teorija
Takmičarsko Znanje
Izbor Radnog Okruženja (IDE)
Osnove
Tvoj Prvi ProgramTipovi podataka, Unos i IzlazC++ sintaksaModuloFunkcijeVektoriMatriceVremenska Složenost Algoritma
Sortiranje
SortiranjeSortiranje PrebrojavanjemRadix Sort
Tehnike Optimizacije
Dva PokazivačaZbir brojeva od 1 do nZbir PrefiksaBinarna PretragaPohlepni AlgoritmiFunkcije Binarne PretrageBinarna Pretraga po RešenjuPodeli, pa Vladaj
Binarni Brojevi
Binarni BrojeviBrojevi u koduOperacije nad BitovimaBitmaske
Matematika
Binarno StepenovanjeProsti BrojeviRastavljanje na proste činioceNZD i NZSEratostenovo SitoModifikovano Sito
Strukture Podataka
Niske (Stringovi)StekRedMapeSkupovi (Set)Red sa PrioritetomKorišćenje Proizvoljnih KriterijumaSegmentna StablaFenvikova StablaSparse TabeleDisjunktni Skupovi
Kombinatorika
Pravilo SabiranjaPravilo MnoženjaKombinatorni ObjektiPrincip Uključenja Isključenja
Geometrija
Osnove GeometrijeVektoriVektorski i Skalarni ProizvodLinijePoligoniUgloviTačka u PoligonuRastojanja i Tačke PresekaKonveksni OmotačKrugovi
Rekurzija
PokazivačiRekurzijaGenerisanje Kombinatornih Objekata
Dinamičko Programiranje
O DP-uDP nad StablimaDP nad BitmaskamaDP nad brojevima
Teorija Grafova
GrafoviDFS i BFSNajkraći PuteviStablaTopološko SortiranjeDajkstrin AlgoritamMinimalna Razapinjuća StablaAlgoritmi Najkraćih Puteva
Napredna Teorija Grafova
Dvostruka PovezanostJako Povezane KomponenteBipartitni GrafMaksimalni Protok u GrafuFord-Fulkersonov AlgoritamDualnost Protoka i Minimalnog PresekaTeško-Laka DekompozicijaCentroidna Dekompozicija
Napredne Strukture Podataka
2D i 3D Segmentna StablaLenjo PropagiranjeImplicitna Segmentna StablaPerzistentna Segmentna StablaNajbliži Zajednički PredakTrieBalansirana Binarna Stabla PretrageMoov Algoritam

Hiršov h-indeks

EasyProblem #32
VremeMemorijaUlazIzlaz
1 s64 MBstdinstdout

Naučnici se rangiraju pomoću statistike koja se zove Hiršov indeks (kraće h-indeks). H-indeks naučnika je najveći broj h takav da naučnik ima bar h radova od kojih svaki ima bar h citata. Za date brojeve citata svih radova jednog naučnika, tvoj zadatak je da izračunaš njegov h-indeks.

Ulaz

U prvoj liniji ulaza je jedan ceo broj t - broj test primera. Svaki test primer čine dve linije:

  • u prvoj je ceo broj n - broj radova
  • a u drugoj je n celih brojeva - broj citata svakog rada.

Izlaz

Za svaki test primer ispiši u posebnoj liniji h-indeks.

Primer

Input
2
8
3 5 12 7 5 9 0 17
3
0 0 0
Output
5
0

U prvom test primeru postoji tačno 5 radova sa bar 5 citata (5,12,7,9,17), ali ne i 6 radova sa bar 6 citata. U drugom nijedan rad nema ni jedan citat, pa je h-indeks 0.

Ograničenja

1≤t≤1000
1≤n≤2⋅105
0≤ai​≤109
n1​+n2​+…+nt​≤2⋅105


Zadatak je, uz dozvolu, preuzet iz zadatka Hiršov h-indeks, čiji su autori Društvo matematičara Srbije i Fondacija Petlja.

Pošalji svoje rešenje

Prijavi se da pošalješ rešenje i pratiš svoj napredak.

Prijavi se