Question

Problema #3902 SortSum de pe pbinfo. Incerc sa o rezolv de 2 zile dar mereu depasesc limita de timp

Answer 1

Răspuns:

#include <fstream>

#include <algorithm>

using namespace std;

ifstream f("sortsum.in");

ofstream g("sortsum.out");

int a[1000002], x, n;

int sum(int n)

{

int s = 0;

while (n)

{

  s += n % 10;

  n /= 10;

}

return s;

}

int main()

{

while (f >> x)

{

  a[n++] = sum(x) * 10000000 + 10000000 - x;

}

sort(a, a + n);

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

{

  g << 10000000 - a[i] % 10000000 << " ";

}

f.close();

g.close();

return 0;

}

Explicație:

Aici ai o rezolvare a problemei folosind functia sort (poti folosi si qsort daca doresti).

In loc sa folosim o functie de comparare cmp ca parametru pentru sort, am decis sa facem o mica smecherie pentru numerele cu valori a sumei cifrelor egale, marindu-le foarte mult, iar dupa aceea scazand din ele nr initial pentru a forma astfel numere diferite ce vor fi ordonate de sort.