На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Поиск Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Сортировка , Сложность N*logN
startinger
Сообщ. #1 ,

    Full Member
    ***
    Профиль · PM
    Рейтинг (т): 10
    На прямой дано N отрезков с координатами (a[i]; b[i]). 1<=i<=N. Найти максимальное k, для которого существет точка на прямой, покрытая k отрезками. За N*logN операций
    albom
    Сообщ. #2 ,
      Senior Member
      ****
      Профиль · PM
      Поощрения: 2 Dgm
      Рейтинг (т): 20
      Вот такой вариант:
      var n,nn,j,i:integer;
         pos:array[1..100]of integer;
         flag:array[1..100]of shortint;
         cur,max:integer;

      procedure sort(l,r: integer);
      var
       i,j,x,y: integer;
      begin
       i:=l; j:=r; x:=pos[(l+r) DIV 2];
       repeat
         while pos[i]<x do i:=i+1;
         while x<pos[j] do j:=j-1;
         if i<=j then
         begin
           y:=pos[i]; pos[i]:=pos[j]; pos[j]:=y;
           y:=flag[i];flag[i]:=flag[j];flag[j]:=y;

           i:=i+1; j:=j-1;
         end;
       until i>j;
       if l<j then sort(l,j);
       if i<r then sort(i,r);
      end;

      begin
      readln(n);
      nn:=n*2;
      j:=1;
      for i:=1 to n do
      begin
      readln(pos[j],pos[j+1]);flag[j]:=+1;flag[j+1]:=-1;inc(j,2);
      end;
      sort(1,nn);
      cur:=0;
      max:=0;
      for i:=1 to nn do
      begin
      inc(cur,flag[i]);
      if cur>max then
       max:=cur;
      end;

      writeln(max);
      end.

      Правда тут используется быстрая сортировка, которая в наихудшем случае дает сложность N^2.
      Просто не вспомнил запись алгоритма древесной сортировки (с максимальной сложностью N*logN).
      esperanto
      Сообщ. #3 ,

        математик
        *****
        Профиль · PM
        Поощрения: 5 Dgm
        Рейтинг (т): 50
        Цитата (albom @ 21.11.03, 17:39)
        Вот такой вариант:
        var n,nn,j,i:integer;
           pos:array[1..100]of integer;
           flag:array[1..100]of shortint;
           cur,max:integer;

        procedure sort(l,r: integer);
        var
         i,j,x,y: integer;
        begin
         i:=l; j:=r; x:=pos[(l+r) DIV 2];
         repeat
           while pos[i]<x do i:=i+1;
           while x<pos[j] do j:=j-1;
           if i<=j then
           begin
             y:=pos[i]; pos[i]:=pos[j]; pos[j]:=y;
             y:=flag[i];flag[i]:=flag[j];flag[j]:=y;

             i:=i+1; j:=j-1;
           end;
         until i>j;
         if l<j then sort(l,j);
         if i<r then sort(i,r);
        end;

        begin
        readln(n);
        nn:=n*2;
        j:=1;
        for i:=1 to n do
        begin
        readln(pos[j],pos[j+1]);flag[j]:=+1;flag[j+1]:=-1;inc(j,2);
        end;
        sort(1,nn);
        cur:=0;
        max:=0;
        for i:=1 to nn do
        begin
        inc(cur,flag[i]);
        if cur>max then
         max:=cur;
        end;

        writeln(max);
        end.

        Правда тут используется быстрая сортировка, которая в наихудшем случае дает сложность N^2.
        Просто не вспомнил запись алгоритма древесной сортировки (с максимальной сложностью N*logN).

        как говорил наш преподаватель я не компилятор напишите идею чтобы было понятно
        Visitor
        Сообщ. #4 ,

          Profi
          *****
          Профиль · PM
          Поощрения: 1 Dgm
          Рейтинг (т): 22
          Честно говоря тоже не очень понял... smile.gif но, _должно_ быть что-то вроде:

          1.Отсортировали все концы отрезков в массив пар (координата, признак начала отрезка):
          2.Двигаемся по етому массиву:
          3.==Очередная координата имеет "признак начала"?
          4.==Да. Увеличиваем число пересекающихся отрезков
          5.====Число пересекающихся отрезков больше последнего запомненного?
          6.====Да. Последнее запомненне = (координата, число отрезков)
          7.====Нет. Пофих.
          8.==Нет. Уменьшаем число пересекающихся отрезков.
          9.Пока массив не кончится.
          Сообщение отредактировано: Visitor -
          startinger
             Сообщ. #5 ,

            Full Member
            ***
            Профиль · PM
            Рейтинг (т): 10
            А если рассмотреть вырожденный отрезок, т.е. точку, то при тестировании алгоритм иногда её считает почему-то, а иногда нет, т.к. сначала добавляет +1, а затем вычитает её приблизительно в том же месте или что-то вроде, т.е. точка засчитывается как 0-отрезок. А нужно считать её за реальный отрезок. Например,
            1 11
            2 12
            3 6
            3 3
            1 7
            3 7
            1 2
            3 3
            Алгоритм должен выдать 7 отрезков.
            3 3
            Алгоритм должен выдать 1 отрезок.
            Как бы поаккуратнее исправить? Просто иногда алгоритм всё-таки считает такие отрезки. Если вспомню тест, выложу.
            albom
            Сообщ. #6 ,
              Senior Member
              ****
              Профиль · PM
              Поощрения: 2 Dgm
              Рейтинг (т): 20
              Ну смотри, в той программе точки сортировались при помощи сранения pos[i]<x.
              А что бы считать вырожденные отрезки, этого сравненея недостаточно.
              Можно даже ввести функцию:
              function less(a,b:integer):boolean;
              begin
              if pos[a]<pos[b] then less:=true
              else if pos[a]>pos[b] then less:=false
              else less:=flag[a]>flag[b]
              end;

              Тогда изменится и процедура sort, вот так:
              procedure sort(l,r: integer);
              var
              i,j,x,y: integer;
              begin
              i:=l; j:=r; x:=(l+r) DIV 2;
              repeat
                while less(i,x) do i:=i+1;
                while less(x,j) do j:=j-1;
                if i<=j then
                begin
                  y:=pos[i]; pos[i]:=pos[j]; pos[j]:=y;
                  y:=flag[i];flag[i]:=flag[j];flag[j]:=y;

                  i:=i+1; j:=j-1;
                end;
              until i>j;
              if l<j then sort(l,j);
              if i<r then sort(i,r);
              end;
              startinger
              Сообщ. #7 ,

                Full Member
                ***
                Профиль · PM
                Рейтинг (т): 10
                Понимаешь, albom, всё бы вроде бы хоршо, но на некоторых
                тестах сортировка, которую ты предлагаешь, даёт сбой.
                Уже при 6 отрезках есть много вариантов, где одно число
                при сортировке становится не на свое место.
                Например,
                2 7 7 7 3 7 5 11 7 7 1 7
                Результат: 1 2 3 7 5 7 7 7 7 7 7 11
                Можно еще затестить варианты:
                1 7 4 7 6 7 5 7 1 7 2 11
                1 10 3 9 9 11 4 7 1 7 3 7
                Даже есть варианты, когда получается совсем печально:
                1 7 3 9 9 11 4 7 1 7 3 7
                Результат: 1 1 3 3 7 4 7 9 9 7 7 11

                Искать недочёт пока нет времени, я тут написал вещь
                пообъёмнее, но вроде работает корректно. В
                сформированном массиве упорядочиваются по убыванию
                флаги у одинаковых элементов массива Pos в
                процедуре flagsort, которая использует процедуру
                invsort-это quicksort по убыванию.
                Но это уже по сложности побольше, чем N*LogN, может
                быть можно оптимизнуть, ну, например, сделать одну
                quicksort, передавая в качестве параметра возраст. или
                убывание делать, и сам массив. Или доработать алгоритм
                albom'а.


                var n,nn,j,i:integer;
                  pos:array[1..100]of integer;
                  flag:array[1..100]of shortint;
                  cur,max:integer;
                  tl,tr:integer; {границы в сортировке массива flag}

                procedure sort(l,r: integer);
                var
                i,j,x,y: integer;
                begin
                i:=l; j:=r; x:=pos[(l+r) DIV 2];
                repeat
                  while pos[i]<x do i:=i+1;
                  while x<pos[j] do j:=j-1;
                  if i<=j then
                  begin
                    y:=pos[i]; pos[i]:=pos[j]; pos[j]:=y;
                    y:=flag[i];flag[i]:=flag[j];flag[j]:=y;

                    i:=i+1; j:=j-1;
                  end;
                until i>j;
                if l<j then sort(l,j);
                if i<r then sort(i,r);
                end;

                procedure invsort(l,r:integer);
                var i,j,x,y:integer;
                begin
                i:=l; j:=r; x:=flag[(l+r) DIV 2];
                repeat
                  while flag[i]>x do i:=i+1;
                  while x>flag[j] do j:=j-1;
                  if i<=j then
                    begin
                    y:=flag[i];flag[i]:=flag[j];flag[j]:=y;
                    i:=i+1; j:=j-1;
                    end;
                until i>j;
                if l<j then invsort(l,j);
                if i<r then invsort(i,r);
                end;

                procedure flagsort;
                var exist:boolean; k:integer;
                begin
                k:=1; tl:=0; tr:=0;
                while k<nn do
                 begin
                 exist:=false;
                 while pos[k]=pos[k+1] do
                   begin
                   exist:=true;
                   if (k>1) and (pos[k]<>pos[k-1]) then tl:=k;
                   inc(k);
                   end;
                 if exist then
                   begin
                   if tl=0 then tl:=1;
                   tr:=k;
                   invsort(tl,tr);
                   end;
                 inc(k);
                 end;
                end;

                begin
                readln(n);
                nn:=n*2;
                j:=1;
                for i:=1 to n do
                begin
                readln(pos[j],pos[j+1]);flag[j]:=+1;flag[j+1]:=-1;inc(j,2);
                end;
                sort(1,nn);
                flagsort;
                cur:=0;
                max:=0;
                for i:=1 to nn do
                begin
                inc(cur,flag[i]);
                if cur>max then
                max:=cur;
                end;

                writeln(max);
                end.
                Visitor
                Сообщ. #8 ,

                  Profi
                  *****
                  Профиль · PM
                  Поощрения: 1 Dgm
                  Рейтинг (т): 22
                  Да вы чего sad.gif

                  Если отрезки змкнутые (включают в себя свои концы), нужно при одинаковой координате первыми ставить начала отрезков, если открытые -- сначала ставить концы. И считать количество пересекшихся -- работает для любых, хоть трижды вырожденных отрезков.
                  startinger
                     Сообщ. #9 ,

                    Full Member
                    ***
                    Профиль · PM
                    Рейтинг (т): 10
                    2Visitor: Ну поподробнее алгоритм можно? На том же pas'е или просто алгоритмически?
                    Visitor
                    Сообщ. #10 ,

                      Profi
                      *****
                      Профиль · PM
                      Поощрения: 1 Dgm
                      Рейтинг (т): 22
                      Паскаля под рукой нет. На Си -- вот:
                      overlay.cpp
                      #include <stdlib.h>
                      #include <stdio.h>

                      typedef struct __tagpoint{
                      double x;
                      int isbegin;
                      } pnt, *ppnt;

                      int compareOpen(const void *ppnt1, const void *ppnt2)
                      {
                      if(((ppnt)(ppnt1))->x > ((ppnt)(ppnt2))->x)
                       return 1;
                      if(((ppnt)(ppnt1))->x < ((ppnt)(ppnt2))->x)
                       return -1;

                      /* Отрезки считаем открытыми, НЕ включающими свои концы */
                      if(((ppnt)(ppnt1))->isbegin < ((ppnt)(ppnt2))->isbegin)
                       return -1;
                      if(((ppnt)(ppnt1))->isbegin > ((ppnt)(ppnt2))->isbegin)
                       return 1;

                      return 0;
                      }

                      int compareClosed(const void *ppnt1, const void *ppnt2)
                      {
                      if(((ppnt)(ppnt1))->x > ((ppnt)(ppnt2))->x)
                       return 1;
                      if(((ppnt)(ppnt1))->x < ((ppnt)(ppnt2))->x)
                       return -1;

                      /* Отрезки считаем замкнутыми, включающими свои концы */
                      if(((ppnt)(ppnt1))->isbegin < ((ppnt)(ppnt2))->isbegin)
                       return 1;
                      if(((ppnt)(ppnt1))->isbegin > ((ppnt)(ppnt2))->isbegin)
                       return -1;

                      return 0;
                      }

                      int main(int argc, char* argv[])
                      {
                      FILE *fin;
                      int N, i;
                      ppnt p;
                      double t;

                      int bestfound, cur;

                      fin = fopen("in.txt", "rt");

                      fscanf(fin, "%d", &N);
                      p = new pnt[N*2];
                      for(i=0; i<N; i++)
                      {
                       fscanf(fin, "%lf", &(p[i*2].x));
                       fscanf(fin, "%lf", &(p[i*2+1].x));
                       if(p[i*2].x > p[i*2+1].x)
                       /* На всякий, вдруг кто начало перед концом напишет... */
                       {
                        t = p[i*2].x;
                        p[i*2].x = p[i*2+1].x;
                        p[i*2+1].x = t;
                       }
                       p[i*2].isbegin = 1;
                       p[i*2+1].isbegin = 0;
                      }

                      fclose(fin);

                      qsort(p, N*2, sizeof(pnt), compareClosed);

                      bestfound = cur = 0;
                      for(i=0; i<N*2; i++)
                       if(p[i].isbegin)
                        if(++cur > bestfound) bestfound = cur; else;
                       else
                        --cur;

                      printf("%d-layer overlay(s) found\n", bestfound);

                      return 0;
                      }

                      in.txt
                      3
                      1 2
                      2 3
                      3 4
                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                      0 пользователей:


                      Рейтинг@Mail.ru
                      [ Script execution time: 0.0808 ]   [ 15 queries used ]   [ Generated: 8.10.26, 00:59 GMT ]  
                      Powered by Invision Power Board(U) v1.2 © 2003  IPS, Inc.