Уменьшить время выполнения программы

@GreenFoxer · Регистрация: 26.04.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте, мне дана задача, на решение которой дан лимит по времени: 400ms. В моем решении на больших числах программа выполняется 401 - 402ms. Тоесть на одну - две милисекунды дольше чем нужно и поэтому задача не проходит. Обидно не правда ли? Помогите мне что то изменить в решении, чтобы программа выполнялась немного быстрее.

Условие
При хранении данных на жестких дисках типа HDD данные группируются по секторам. Все файлы разбиваются на фрагменты, которые в свою очередь записываются в некоторых секторах жесткого диска. При этом сектора, в которых находится один файл не обязательно следуют друг за другом и могут располагаться в произвольном порядке.
Одной из проблем HDD-носителей является то, что магнитная головка должна перемещаться от одного сектора к другому, чтобы считать один файл.
Вам требуется определить время за которое будет считан файл, разбитый на n фрагментов. В i-м секторе записан фрагмент файла номер fi (1<=fi<=n). При этом в различных секторах находятся в различные фрагменты. Будем считать, что изначально магнитная головка находится в секторе, в котором записан первый фрагмент. Считывание происходит следующим образом: сначала считывается первый фрагмент, затем магнитная головка перемещается к сектору, содержащему второй фрагмент, считывается второй фрагмент и так далее пока не будет считан n-й фрагмент. Фрагменты считываются один за другим по порядку от 1-го до n-го.
На перемещение магнитной головки от a-го сектора до b-го уходит |a-b| единиц времени. Временем считывания информации можно пренебречь.

Решение

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var a,b,w,f:array[1..200000] of longint;
p,n,i,k,l,sch, nom:longint;
begin
read(n);
for i:=1 to n do
begin
read(a[i]); b[i]:=a[i]; end;
for l:=1 to n-1 do
for i:=l+1 to n do
if a[l] >  a[i] then
begin
p:=a[l];
a[l]:=a[i];
a[i]:=p;
end;
i:=1; l:=1;
while (i<=n) and (l<=n+1) do
begin
if a[i]=b[l] then w[i]:=l; 
l:=l+1;
if l=n+1 then begin i:=i+1; l:=1; end;
end;
sch:=0;
for i:=2 to n do
sch:=sch+abs(w[i]-w[i-1]);
writeln(sch);
end.

ФедосеевПавел · 20.02.2016, 18:59

А зачем сортировать, если

Сообщение от GreenFoxer

Считывание происходит следующим образом: сначала считывается первый фрагмент, затем магнитная головка перемещается к сектору, содержащему второй фрагмент, считывается второй фрагмент и так далее пока не будет считан n-й фрагмент. Фрагменты считываются один за другим по порядку от 1-го до n-го.

Т.е. без оптимизации перемещения головки?

Добавлено через 47 секунд
И каковы ограничения на диапазоны значений переменных?

@GreenFoxer · 20.02.2016, 19:12 **[ТС]**

Сообщение от ФедосеевПавел

И каковы ограничения на диапазоны значений переменных?

2*10^5

ФедосеевПавел · 20.02.2016, 19:19

Нашёл эту задачу с примерами и пояснениями.
Для её решения нужно получить список секторов файла, упорядоченных по возрастанию номера фрагмента, в то время как на входе - последовательность, упорядоченная по номеру сектора.

Наверное нужно считывать в массив так

Pascal
1
2
3
4
5
6
7
8
9
10
  readln(n);
  for i:=1 to n do
  begin
    read(fi);
    a[fi]:=i;
  end;
а теперь обработка
  t:=0;
  for i:=2 to n do
    t:=t+abs(a[i]-a[i-1]);

@GreenFoxer · 20.02.2016, 19:30 **[ТС]**

Сообщение от ФедосеевПавел

Нашёл эту задачу с примерами и пояснениями.

Ты не совсем правильно понял задачу. считывание идет не по порядку, а от меньшего символа к большему.
Например цикл: 2 4 5 1...
нужно начинать с 1, тоесть с четвертого номера, потом 2, тоесть 1 номер и так далее. А потом обработка t:=t+abs(1-4)

ФедосеевПавел · 20.02.2016, 19:44

Ну, не "ты", а "вы". А во вторых - правильно понял, и правильно реализовал.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
program test;
 
var
  a: array of dword;
  i, n, fi, t: dword;
begin
  Assign(input, '612b.txt');
  reset(input);
  readln(n);
  setlength(a, n);
  for i := 1 to n do
  begin
    Read(fi);
    a[fi - 1] := i;
  end;
 
  for i := 0 to n - 1 do
    Write(a[i]: 3);
  writeln;
 
  t := 0;
  for i := 1 to n-1 do
    t := t + abs(a[i] - a[i - 1]);
  writeln(t);
end.

для входных данных

Code
5
1 3 5 4 2

получаю 10 - как в пояснении к задачи.

@GreenFoxer · 20.02.2016, 20:54 **[ТС]**

Сообщение от ФедосеевПавел

правильно реализовал

Dword??? Что это вообще за тип данных. Например ABC Pascal с таким кодом вообще не компилирует...

@bormant · 20.02.2016, 21:11

Longint-а хватит за глаза.

Добавлено через 9 минут

Сообщение от GreenFoxer

Dword??? Что это вообще за тип данных

Двойное беззнаковое целое. ABC Pascal много чего не компилирует, что ж тут поделаешь...

@GreenFoxer · 20.02.2016, 21:24 **[ТС]**

Сообщение от bormant

ABC Pascal много чего не компилирует

А можно версию, чтобы скомпилировало?

ФедосеевПавел · 20.02.2016, 21:56

Сообщение от bormant

Longint-а хватит за глаза.

Заменить dword на longint

Добавлено через 8 минут
А простой вопрос - на том сайте среди компиляторов присутствует Pascal ABC?

@GreenFoxer · 20.02.2016, 21:57 **[ТС]**

Сообщение от ФедосеевПавел

Заменить dword на longint

А что за файл считывается? (612b)

ФедосеевПавел · 20.02.2016, 22:19

Я привёл не готовый для сдачи код, а продемонстрировал алгоритм. Чтобы не набирать каждый раз исходные данные во время отладки - сохранил их в файл.
Вы можете самостоятельно переработать этот пример.

Добавлено через 15 минут

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
program test;
 
var
  a: array of longint;
  i, n, fi, t: longint;
begin
  readln(n);
  setlength(a, n);
  for i := 1 to n do
  begin
    Read(fi);
    a[fi - 1] := i;
  end;
  t := 0;
  for i := 1 to n - 1 do
    t := t + abs(a[i] - a[i - 1]);
  writeln(t);
end.

@GreenFoxer · 20.02.2016, 23:34 **[ТС]**

Да, действительно работает. Благодарю.

Добавлено через 10 минут

Сообщение от GreenFoxer

Да, действительно работает.

Хотя все равно проходит не все тесты. На одном из тестов происходит выход за границы допустимых значений.

@Somebody · 20.02.2016, 23:46

Сообщение от GreenFoxer

В моем решении на больших числах программа выполняется 401 - 402ms. Тоесть на одну - две милисекунды дольше чем нужно и поэтому задача не проходит. Обидно не правда ли?

Всего на одну-две, скорее всего, только потому, что по истечении отведённого времени программа прибивается. Сколько бы она на самом деле работала - неизвестно.

ФедосеевПавел · 21.02.2016, 08:42

Сообщение от GreenFoxer

На одном из тестов происходит выход за границы допустимых значений.

Увеличить разрядность t до int64.

@GreenFoxer · 21.02.2016, 11:26 **[ТС]**

Сообщение от ФедосеевПавел

Увеличить разрядность t до int64.

Да, спасибо, работает.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .