# PBinfo #4337 – normalizare – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dă un șir de n numere întregi a = (a[1], a[2], ..., a[n]). Trebuie să construiți un nou vector b de lungime n în care valorile sunt cuprinse între 1 și n astfel: toate elementele a[i] care memorează valoarea minimă se înlocuiesc în b[i] cu 1, toate elementele a[j] imediat mai mari decât minimele se înlocuiesc în b[j] cu 2, ș.a.m.d. De exemplu, dacă a = (7,-3,1,-55,20,7,-3,1), atunci b = (4,2,3,1,5,4,2,3). Se observă că valoarea minimă -55 apare o singură dată la poziția 4, deci b[4] = 1, valoarea imediat mai mare decât minimul este -3 deci b[2] = 2 și b[7] = 2, următoarea valoare este 1, deci b[4] = 3 și b[8] = 3. Urmează valoarea 7, deci b[1] = 4 și b[6] = 4. În fine, cea mai mare valoare este 20 și va fi marcată în b cu 5.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi șirul a de n numere întregi, separate prin spații.

Date de ieșire
Programul va afișa pe ecran, separate prin spații, cele n elemente ale șirului b.

Restricții și precizări

1 ≤ n ≤ 100.000
cele n elemente ale șirului a vor fi întregi din intervalul [-2.000.000.000, 2.000.000.000]

Exemplu:
Intrare

8
7 -3 1 -55 20 7 -3 1
Ieșire

4 2 3 1 5 4 2 3

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
struct Triplet
{
    int val, ind, newval;
};
Triplet a[100002];
int n;
bool Compara1(Triplet A, Triplet B)
{
    return A.val < B.val;
}
bool Compara2(Triplet A, Triplet B)
{
    return A.ind < B.ind;
}
int main()
{
    int i;
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> a[i].val;
        a[i].ind = i;
    }
    sort(a + 1, a + n + 1, Compara1);
    a[1].newval = 1;
    for (i = 2; i <= n; i++)
        if (a[i].val == a[i - 1].val) a[i].newval = a[i - 1].newval;
        else a[i].newval = 1 + a[i - 1].newval;
    sort(a + 1, a + n + 1, Compara2);
    for (i = 1; i <= n; i++)
        cout << a[i].newval << " ";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4337)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4337/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4337/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)