Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 09.10.2015, 15:40   #1
VladKB1
Форумчанин
 
Регистрация: 21.05.2014
Сообщений: 121
Радость Вывести индекс 1-ой высоты которая выше данной (FreePascal)

Всем привет!

Я хочу обратиться за помощью. Мой код для задачи (условие ниже) не проходит 2 последних теста по времени.
Я новерно знаю из-за чего мой код медленно работает, но я не знаю чем можно замить этот участок.

Условие задачи:

N (1 <= N <= 100,000) коров Фермера Джона, пронумерованных
последовательно 1..N стоят в ряд. Корова i имеет высоту
H_i (1 <= H_i <= 1,000,000).

Каждая корова i смотрит в направлении с большими индексами.
Мы говорим, что корова "смотрит вверх" на корову j если i<j
и H_i < H_j. Для каждой коровы i ФД хочет знать индекс первой
коровы, на которую корова i <смотрит вверх>.

Замечание: около 50% тестов будут иметь N <= 1,000.

INPUT FORMAT:

* Строка 1: Одно целое число: N

* Строки 2..N+1: Строка i+1 содержит одно целое число: H_i

SAMPLE INPUT (file lookup.in):

6
3
2
6
1
1
2

INPUT DETAILS:

У ФД 6 коров с высотами 3, 2, 6, 1, 1, 2.

OUTPUT FORMAT:

* Строки 1..N: Строка i содержит одно целое число,
представляющее наименьший индекс коровы,
на которую данная "смотрит вверх".
Если такой коровы нет - выводите 0.

SAMPLE OUTPUT (file lookup.out):

3
3
0
6
6
0

OUTPUT DETAILS:

Коровы 1 и 2 обе "смотрят вверх" на корову 3; коровы 4 и 5
обе смотрят вверх на корову 6; коровы 3 и 6 не "смотрят
вверх" ни на одну из коров.



Мой код:

Код:
var
 st,b,a,max,maxI: array [1..100001] of longint;
 stn,i,n,j,f,y: longint;
begin
 assign(input,'lookup.in');
 reset(input);
 assign(output,'lookup.out');
 rewrite(output);

 stn:=100001;
 readln(n);
 for i:=1 to n do readln(a[i]);
 for i:=n downto 1 do
 begin
  f:=0;
  dec(stn);
  st[stn]:=a[i];
  if st[stn] < st[stn+1] then
  begin
   inc(j);
   max[j]:=st[stn+1];
   maxI[j]:=i+1;
   b[i]:=i+1;
   f:=1;
  end else
  for y:=j downto 1 do if st[stn] < max[y] then  //я так полагаю из-за этого перебора высот коров, оно и слетает по времени,я прав?
  begin
   b[i]:=maxI[y];
   f:=1;
   break;
  end;
  if f = 1 then continue;
  b[i]:=0;
 end;

 for i:=1 to n do writeln(b[i]);
end.
Всем кто поможет заранее огромное спасибо!

Последний раз редактировалось VladKB1; 10.10.2015 в 01:30.
VladKB1 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Программа, которая отгадает животное задав 4 - 5 вопросов по данной картинке Rio3051 Паскаль, Turbo Pascal, PascalABC.NET 5 14.12.2014 20:21
Функция, которая возвращает индекс первого элемента harvey Помощь студентам 4 29.03.2013 14:47
Как вывести картинку определенной высоты АлександрСмирнов Помощь студентам 1 15.06.2012 08:01
Составить программу которая находит индекс числа в массиве случайных чисел MadNikys Помощь студентам 9 03.03.2010 20:52
вывести элементы выше главной диагонали : Rusl92 Помощь студентам 0 30.10.2009 22:45