Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28584

Re: problem z algorytmiki

Show all headers | View raw

On 15.05.2016 08:02, slawek wrote:
> On Wed, 11 May 2016 10:38:43 +0200, bartekltg <bartekltg@gmail.com> wrote:
>> więc być mozę da się prościej. Na szybko nie widzę.
>
> Na szybko: posortuj po x, posortuj po y; dla danego punktu znajdź mu
> najbliższy (dzięki sortowaniu masz czterech kandydatów lub mniej); usuń
> parę. Powtarzaj aż do skutku. Rób to kolejno  od najbliższej pary.
> Odległości par możesz obliczyć i posortować, a potem usuwać już
> nieobecne. Całość celuje w O(N log N).

Kontrprzykład:

A1     <-2m->     B1  <-1m->  A2      <-2m->      B2

Optymalne rozwiązanie wiąże A1-B1 B2-A2  na kwotę 4m.

Rozwianie zachłanne daje A1-B2 B1-A2 na kwotę 6m.

pzdr
bartekltg

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

problem z algorytmiki "M.M." <mmarszik@gmail.com> - 2016-05-11 01:01 -0700
  Re: problem z algorytmiki bartekltg <bartekltg@gmail.com> - 2016-05-11 10:38 +0200
    Re: problem z algorytmiki "M.M." <mmarszik@gmail.com> - 2016-05-11 01:46 -0700
    Re: problem z algorytmiki slawek <fake@fakeemail.com> - 2016-05-15 08:02 +0200
      Re: problem z algorytmiki Wojciech Muła <wojtek.mula@gmail.com> - 2016-05-14 23:33 -0700
        Re: problem z algorytmiki "M.M." <mmarszik@gmail.com> - 2016-05-15 05:07 -0700
          Re: problem z algorytmiki bartekltg <bartekltg@gmail.com> - 2016-05-15 19:35 +0200
      Re: problem z algorytmiki bartekltg <bartekltg@gmail.com> - 2016-05-15 19:44 +0200
      Re: problem z algorytmiki bartekltg <bartekltg@gmail.com> - 2016-05-15 20:24 +0200

csiph-web