Rezolvare PBinfo #3624

Decorative Icon Problema: bal1 / 3624

Decorative IconAutor: Andrei

Tocmai a ajuns la balul din sat un grup de n fete numerotate de la 1 la n. Acolo sunt așteptate de m băieți frumoși, numerotați de la 1 la m. Fiecare băiat i (i=1..m) are un coeficient de frumusețe b[i]. Fetele nu acceptă orice băiat la dans. Fata i va accepta să danseze cu un băiat doar dacă băiatul are un coeficient de frumusețe mai mare sau egal cu f[i].

Cerința

Cunoscând coeficienții de frumusețe ai băieților, b[1], b[2], …, b[m] precum și coeficienții preferințelor fetelor, f[1], f[2], …, f[n], să se determine numărul maxim de perechi de dansatori care se poate forma.

Date de intrare

Fișierul de intrare bal.in conține pe prima linie numerele n și m. Pe a doua linie sunt n numere naturale separate prin spații f[1], f[2], …, f[n] reprezentând coeficienții fetelor, iar pe a treia linie sunt numerele b[1], b[2], …, b[m] reprezentând coeficienții băieților.

Date de ieșire

Fișierul de ieșire bal.out va conține un singur număr natural P, reprezentând numărul perechilor (f[i], b[j]) care se poate forma astfel încât f[i] ≤ b[j].

Restricții și precizări
  • 1 ≤ n, m ≤ 100.000
  • coeficienții băieților și fetelor sunt numere naturale nenule mai mici sau egale cu 1.000.000.000
Exemplu:

bal.in

3 3
4 1 5
2 6 3

bal.out

2

Explicație

Sunt trei fete și trei băieți. Se pot forma doar două perechi: (1,2) și (4,6)

Andrei Frîntu
Andrei Frîntu

Fondatorul platformei - mentor Academia

LinkedIn Instagram GitHub
© Copyright 2024 - CodulLuiAndrei.ro - Toate drepturile sunt rezervate