Cerința

Un flic este o creatură pufoasă de dimensiunea unui hamster, având trei ochi și o blană colorată. De la naștere, fiecărui flic îi place în mod deosebit un anumit număr.

Hobby-ul lor este să intre în cutii, iar în lumea flicilor, pe fiecare cutie este inscripționat un număr. Flicii sunt pretențioși și nu vor alege orice cutie. În mod ideal, ar alege cutia pentru care numărul inscripționat este cel mai apropiat de numărul lor favorit, dar pentru că flicii sunt altruiști, vor alege cutiile astfel încât ceilalți flici să nu se supere prea tare.

Astăzi s-a format un grup de n flici, fiecare cu un număr favorit, care au la dispoziție n cutii, fiecare având inscripționat un număr. Sarcina ta este să stabilești pentru fiecare flic în ce cutie va intra, astfel încât suma modulelor diferențelor dintre numărul favorit a flicului și cel inscripționat pe cutia în care intră acesta să fie minimă.

Date de intrare

Fișierul de intrare flici.in conține pe prima linie numărul n; a doua linie conține n numere naturale separate prin spații, reprezentând numerele favorite ale flicilor, iar a treia linie conține n numere naturale separate prin spații, reprezentând numerele inscripționate pe cutii.

Date de ieșire

Fișierul de ieșire flici.out va conține pe prima linie numărul S, reprezentând suma minimă obținută.

Restricții și precizări

1 ≤ n ≤ 100.000
numerele favorite și cele inscripționate sunt numere naturale mai mici sau egale cu 10.000
pentru 40% din punctaj, n < 10
pentru 80% din punctaj, n ≤ 1.000

Exemplu

flici.in

3
1 1 3
1 2 2

flici.out

Explicație

Flicul 1 va intra în cutia 1, flicul 2 în a doua, flicul 3 în a treia, rezultând suma
|1-1| + |1-2| + |3-2| = 2.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Flici:

//Complexitate O(N * logN) timp O(N) memorie
//Greedy cu Quicksort

#include <fstream>
using namespace std;

ifstream fin ("flici.in");
ofstream fout ("flici.out");

const int N = 1e5 + 5;

int v[N], c[N], n, sol;

int abs (int x) {
    return x > -x ? x : -x;
}

void Quicksort (int v[], int left, int right) {
    int i = left, j = right, pivot = v[abs((i + j) >> 1)];
    while (i <= j) {
        while (v[i] < pivot)
            i++;
        while (v[j] > pivot)
            j--;
        if (i <= j) {
            swap (v[i], v[j]);
            i++, j--;
        }
    }
    if (left < j)
        Quicksort (v, left, j);
    if (i < right)
        Quicksort (v, i, right);
}

int main() {
    fin >> n;
    for (int i = 0; i < n; ++i)
        fin >> v[i];
    for (int i = 0; i < n; ++i)
        fin >> c[i];
    Quicksort (v, 0, n-1);
    Quicksort (c, 0, n-1);
    for (int i = 0; i < n; ++i)
        sol += abs (v[i] - c[i]);
    fout << sol;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #556 Flici

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #556 Flici de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #556 Flici