Осталось мало ! 15 ! нужно ускорить работу программы по нахождению количества различных элементов в массиве. массив достигает до 100 000 элементов, а сами элементы до 2 000 000 000. код написан снизу. можно что-то добавить или изменить, можно вообще другой код написать. 15 чистых . язык паскаль (free pascal compiler 3.0.0). надеюсь на вашу var a, b: array [1..100000] of int64; i, n, c, j: longint; tratata, d: boolean; begin readln(n); for i : = 1 to n do begin read(a[i]); if a[i] = 0 then tratata : = true; d : = false; for j : = 1 to n do if a[i] = b[j] then d : = true; if not d then begin inc(c); b[c] : = a[i]; end; end; if tratata then writeln(c + 1) else writeln(c); end.
271
311
Ответы на вопрос:
Из небольших ускорений можно предложить проверять до b[c], дальше всё равно ничего нет. но всё равно алгоритм будет делать порядка n^2 операций, что при n = 10^5 достаточно много. кстати, 2*10^9 еще помещается в longint, int64 не нужен. можно пойти другим путём. отсортируем массив a[i] за n log n, а потом для того, чтобы определить уникальные элементы, достаточно одного прохода по массиву. я буду сортировать сортировкой слиянием, вы можете использовать любую другую достаточно быструю сортировку. procedure merge(var a: array of longint; left1, right1, left2, right2: integer); var temp: array of longint; i, j, k: integer; begin setlength(temp, right1 - left1 + right2 - left2 + 2); i : = left1; j : = left2; k : = 0; while (i < = right1) and (j < = right2) do begin if a[i] < = a[j] then begin temp[k] : = a[i]; inc(i); end else begin temp[k] : = a[j]; inc(j); end; inc(k); end; while i < = right1 do begin temp[k] : = a[i]; inc(k); inc(i); end; while j < = right2 do begin temp[k] : = a[j]; inc(k); inc(j); end; for i : = left1 to right1 do a[i] : = temp[i - left1]; for j : = left2 to right2 do a[j] : = temp[j - left2 + right1 - left1 + 1]; end; procedure mergesort(var a: array of longint; left, right: integer); var t: longint; begin if right - left = 0 then exit; if right - left = 1 then begin if a[left] > a[right] then begin t : = a[left]; a[left] : = a[right]; a[right] : = t; end; exit; end; mergesort(a, left, (left + right) div 2); mergesort(a, (left + right) div 2 + 1, right); merge(a, left, (left + right) div 2, (left + right) div 2 + 1, right); end; var a: array of longint; i, n, count: integer; begin read(n); setlength(a, n); for i : = 0 to n - 1 do read(a[i]); mergesort(a, 0, n - 1); count : = 1; for i : = 1 to n - 1 do if a[i] < > a[i - 1] then inc(count); writeln(count); end.
Один текстовый символ=байт i=53 x 45 x 224 байт =534240 байт =521,72 кбайт =0.51 мбайт(< 1.44 мбайт) необходима одна дискета
Популярно: Информатика
-
HelpinEnglish20.09.2021 07:54
-
raya32304.09.2020 01:04
-
asdads123sad123asds07.10.2022 01:40
-
Martina1726.04.2021 01:50
-
диёра201001.10.2022 07:56
-
pavy198025.06.2023 03:47
-
alisa554027.11.2022 18:31
-
FiveKh12.04.2020 20:03
-
olyazyuzko201714.02.2021 10:55
-
ilyuza2004p06tr412.10.2022 21:27