Question

Alexandru, mare informatician, a decis să își impresioneze prietenii cu următoarea problemă: Dându-se un vector cu N numere naturale nenule, se întreabă care este numărul minim de mulțimi cu numere consecutive de forma {1...K} în care acesta poate fi împărțit. Spre exemplu vectorul A = {1, 3, 2, 2, 1, 4} poate fi împărțit în număr minim de partiții astfel {1, 2, 3, 4}, {1, 2}.

Cerința
Cum această problemă a fost prea dificilă pentru prietenii săi, Alexandru te roagă pe tine să o rezolvi.

Date de intrare
Fișierul de intrare mmult.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații.

Date de ieșire
Fișierul de ieșire mmult.out va conține pe prima linie numărul S, reprezentând răspunsul problemei date de Alex.

Restricții și precizări
1 ≤ N ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000
dacă problema nu are soluție, se va afișa -1

Exemplu
mmult.in

6
1 3 2 2 1 4
mmult.out

2

#2032

Answer 1

Răspuns:

#include <fstream>

using namespace std;

int f[1000000];

int main(){

int n,x, m= 0;

ifstream fin("mmult.in");

ofstream fout("mmult.out");

fin>>n;

for(int i = 0; i < n; i++){

fin >> x;

if(x > m) m = x;

f[x]++;

}

fin.close();

int r = f[1];

int prev = f[1];

for(int i = 2; i <= m; i++){

if(f[i] > prev){r = -1; break;}

prev = f[i];

}

fout << r;

fout.close();

}

Se face cu un vector de frecventa.

Raspunsul este f[1] daca este monoton descrescator sau -1 altfel.