• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Sortowanie Zadanie

VPS Starter Arubacloud
+2 głosów
399 wizyt
pytanie zadane 4 lutego 2017 w C i C++ przez Scypyon Gaduła (3,450 p.)

Treść zadania:

"W szeregu zbiórka!" – krzyknął nauczyciel wychowania fizycznego. Dzieci na rozkaz ustawiły się w szeregu, zachowując odstęp 1 metra, ale zapomniały o porządku reprezentowanej grupy. Patrząc od lewej, najpierw powinna stać grupa Dyniowa, a potem grupa Czekoladowa. Nauczyciel bardzo szybko się denerwuje, dlatego aby uniknąć problemów uczniowie muszą niepostrzeżenie zamienić się miejscami. Akcja będzie przeprowadzona sprawnie, jeśli sumaryczna droga, jaką pokonają dzieci, będzie możliwie najmniejsza.

 

Wejście:

W pierwszym wierszu standardowego wejścia podano liczbę dzieci w szeregu n (1 6 n 6 106 ). W drugim wierszu znajduje się opis szeregu w postaci n znaków D (osoba z grupy Dyniowej) lub C (osoba z grupy Czekoladowej).

Wyjście:

W pierwszym wierszu standardowego wyjścia powinna znaleźć się minimalna suma odległości, jaką muszą pokonać dzieci, aby poprawnie się ustawić.

Przykłady:

Wejście:

4

CDCC

Wyjście:

2

Mój kod:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,x;
    cin>>n;
    string litery[n];
    for(int i=0;i<n;i++)
    {
        cin>>litery[i];
    }
    sort(litery, litery+n);
    for(int i=0;i<n;i++)
    {
    cout<<setw(3)<<litery[i];
    }

    return 0;
}

Problem:

Jak widać samo sortowanie nie jest problemem, nie wiem jak policzyć drogę, którą muszą przebyć te litery, mógłbyś ktoś dać jakąś wskazówkę? 

 

komentarz 4 lutego 2017 przez 10kw10 Pasjonat (22,880 p.)
Moglbys dac link do zadania, jesli to zadanie jest ze spoja ? Zrobilem i ciekawy jestem czy mi przyjmie.
komentarz 4 lutego 2017 przez Scypyon Gaduła (3,450 p.)
Znaczy to jest zadanie z konkursu, zadania oig i tylko uczniowie mojej szkoły mogą brać udział
komentarz 4 lutego 2017 przez 10kw10 Pasjonat (22,880 p.)
aha, wyglada jak ze spoja, nie wazne, zrobilem tak ze posortowalem babelkowo i jesli trzeba bylo zamienic to dodawalem 2 do zmiennej odpowiadajacej za przesuniecie. 2 dlatego ze i jedni musza zmienic pozycje (przejsc o 1 metr) i drudzy, ale nie wiem czy dobrze mysle.
komentarz 4 lutego 2017 przez Scypyon Gaduła (3,450 p.)
Tak, tylko masz pomysł jak to w kodzie(algorytm liczący te przejścia) umieścić? Ja jestem blady przy tym;/
komentarz 4 lutego 2017 przez Adrian Spora Mądrala (5,100 p.)

Można stworzyć zmienną przed funkcją sortującą, tak aby była globalna dla tej funkcji i zwiększać ją o 2 za każdym razem, gdy warunek przestawienia dwóch sąsiednich elementów jest spełniony, tzn w pseudokodzie:

Jeśli obecny element jest większy od następnego (w tym przypadku jeśli obecny == C i następny == D) to: 

  1. Zamień te elementy miejscami
  2. Podnieś wartość zmiennej odleglosc o 2

 

komentarz 4 lutego 2017 przez draghan VIP (106,230 p.)

Znaczy to jest zadanie z konkursu, zadania oig i tylko uczniowie mojej szkoły mogą brać udział

Mógłbyś to wyjaśnić? Zrozumiałem to tak, że bierzesz udział w olimpiadzie i poszukujesz rozwiązań zadań u nas. Mam nadzieję, że się mylę.

komentarz 4 lutego 2017 przez Scypyon Gaduła (3,450 p.)
To nie jest żadna olimpiada, szkolny "konkurs", z nędzną nagrodą "pierwszeństwo w rejestracji na kursy, konkursu i tak nie wygram, bo są u nas takie asy co już dawno wszystko zrobiły, a ja po prostu chce zrozumieć te zadanka, mogę ci podesłać screna z rankingu.
komentarz 4 lutego 2017 przez Scypyon Gaduła (3,450 p.)
Dzięki vector, rozumiem doskonale :)
komentarz 4 lutego 2017 przez draghan VIP (106,230 p.)

To nie jest żadna olimpiada, szkolny "konkurs", z nędzną nagrodą "pierwszeństwo w rejestracji na kursy, konkursu i tak nie wygram, bo są u nas takie asy co już dawno wszystko zrobiły, a ja po prostu chce zrozumieć te zadanka, mogę ci podesłać screna z rankingu.

Nie, w porządku. ;)

1 odpowiedź

+1 głos
odpowiedź 4 lutego 2017 przez vector Dyskutant (9,200 p.)
wybrane 5 lutego 2017 przez Scypyon
 
Najlepsza

Można zastanowić się nad przesuwaniem literek D w taki sposób aby na końcu otrzymać słowo postaci DD....DCC....C.

Najpierw zastanówmy się ilość ruchów potrzebnych do przesunięcia jakiejś literki na pozycji i na pozycję j. literka którą przesuwamy pokona odległość równą |i-j|, a wszystkie literki pomiędzy przesuną się o 1. Tych literek jest również |i-j| więc sumaryczna odległość to 2|i-j|.

Weźmy sobie jakiś przykładowy ciąg CCDCCD. Przeglądając go od lewej do prawej jeżeli jesteśmy aktualnie na literce C, a po prawej stronie są jakieś literki D to trzeba przesunąć którąś tą literkę na miejsce literki C. Optymalnie jest zamienić z najbliższą literką D. Wykonujesz algorytm dopóki po prawej stronie od aktualnej pozycji masz jakieś literki D.

CCCDCCD  => +6 => DCCCCCD => +10 => DDCCCCC. Jak widać wynik to 16

Mniej więcej kod może wyglądać tak: (działa czasowo w O(n lg n))

std::set<int32_t> pos;
std::string str;
std::cin >> str;

for(uint32_t i = 0; i < str.size(); ++i) {
    if(str[i] == 'D') {
        pos.insert(i);
    }
}

int32_t result = 0;
for(uint32_t i = 0; i < str.size(); ++i) {
    if(str[i] == 'D') {
        pos.erase(i);
        continue;
    }

    auto found = pos.lower_bound(i);
    if(found == pos.end()) {
        break;
    }

    result += 2*(*found - i);
    pos.erase(found); 
}

 

Podobne pytania

0 głosów
1 odpowiedź 191 wizyt
pytanie zadane 21 czerwca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 170 wizyt
pytanie zadane 10 stycznia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
2 odpowiedzi 315 wizyt
pytanie zadane 23 kwietnia 2016 w C i C++ przez Koki Nowicjusz (140 p.)

92,454 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...