Cześć,
mam takie zadanie:
http://solve.edu.pl/contests/download_desc/1922
Powiem szczerze nie wiem jak się za nie zabrać :-(
Może ktoś ma pomysł, wskazówkę?
Myślałem o sortowaniu ale książki należy układać zgodnie z kolejnością alfabetyczną:-)
0
1
Próbowałeś brute forca? Nie zakładam, że to przejdzie, ale to na pewno pomogłoby ci lepiej zrozumieć problem. Jak już się ma brute forca łatwiej dostrzec możliwe udoskonalenia. Mi od razu przychodzi do głowy takie coś: Trzeba zapisać wartości w tablicy i co najmniej 2 razy po niej iterować. W pierwszej policzyć łączną szerokość książek i znaleźć najszerszą książkę. Dzielimy łączną szerokość książek przez ilość regałów. Większe spośród wyniku tego dzielenia i max. szerokości książki to taki pierwszy strzał, który można by sprawdzić w 2 iteracji i potem próbować znowu i znowu metodą prób i błędów. Prawdopodobnie i to nie będzie wystarczające, jest wiele możliwych optymalizacji. Jedno podejście jest takie, żeby nie próbować wszystkich możliwości pod rząd tylko uzależniać zmianę oszacowanej wartości od wyniku, trzeba tylko wymyślić mądrą heurystykę (pewnie ilość brakującego miejsca jest jakimś strzałem). Drugie podejście jest takie, żeby iterując po tablicy szukać najlepiej rokujących miejsc i tylko na nich pracować. Inna opcja jest taka, żeby w drugiej iteracji stworzyć tablicę zbiorów książek - dla każdego zbioru przechowujesz wskaźniki do pierwszego i ostatniego elementu oraz łączną szerokość. Dzięki temu zamiast w kółko iterować po całej tablicy można się skupić na granicach między zbiorami. Możliwości jest dużo, próbuj. :D
0
Mam taki kod ale nie przechodzi wszystkich testów:(
#include <iostream>
using namespace std;
long long int tab1[500005];
int main ()
{
std::ios_base::sync_with_stdio (false);
cin.tie (0);
cout.tie (0);
int n=0,k=0, max=0, srednia=0;
long long int suma=0;
cin>>n>>k;
for (int i=0; i<n; i++)
{
cin>>tab1[i];
suma=suma+tab1[i];
}
max = tab1[n-1];
for (int i = 0; i< n; ++i)
{
if (max <= tab1[n-i-1])
max = tab1[n-i-1];
}
if ((suma>=k)&& (suma%k==0))
{
srednia=suma/k;
}
else
{
srednia=(suma/k)+1;
}
if (srednia>max)
{
cout<<srednia;
}
else
{
cout<<max;
}
}
0
Ledwie zacząłeś próbować to co napisałem. ;P Jak masz treść testów to sprawdź w jakim przypadku nie przechodzi testu i przeanalizuj go. A bez testów to to nie jest forum dla wróżek, nikomu chyba nie chce się poświęcać tyle czasu żeby dochodzić każdej możliwości. Z resztą to jest TWOJE zadanie.
0
elwis napisał(a):
Ledwie zacząłeś próbować to co napisałem. ;P Jak masz treść testów to sprawdź w jakim przypadku nie przechodzi testu i przeanalizuj go. A bez testów to to nie jest forum dla wróżek.
Nie znam treści testów :(
0
To w takim razie chyba będziesz musiał napisać je samemu. Stwórz dane testowe, sprawdzające możliwie trudne przypadki i stwórz skrypt, który automatycznie będzie je sprawdzać. Tak swoją drogą, przecież ty tylko wziąłeś te dwie wartości o których pisałem i po prostu je wypisałeś. NIc dziwnego, że nie przechodzi testu. Stworzenie przypadku w którym to nie działa nie jest trudne. :P
0
Zadanie zrobiłem.
#include <bits/stdc++.h>
using namespace std;
long long int tab[500005];
int main ()
{
long long int n,k, suma1=0;
cin>>n>>k;
for (int i=0; i<n; i++)
{
cin>>tab[i];
suma1+=tab[i];
}
long long int lewo=0, prawo=suma1, d;
while (prawo-lewo>1)
{
long long int odp=1;
d=(prawo+lewo)/2;
long long int p=0;
long long int suma=0;
for (int i=0; i<n; i++)
{
if (tab[i]>d)
{
odp=0;
}
if (suma+tab[i]>d)
{
suma=tab[i];
p++;
}
else
{
suma+=tab[i];
}
}
if (suma>0)
{
p++;
}
if(p>k)
{
odp=0;
}
if (odp==1)
{
prawo=d;
}
else
{
lewo=d;
}
}
if (lewo!=prawo)
{
long long int odp=1;
d=lewo;
long long int p=0;
long long int suma=0;
for (int i=0; i<n; i++)
{
if (tab[i]>d)
{
odp=0;
}
if (suma+tab[i]>d)
{
suma=tab[i];
p++;
}
else
{
suma+=tab[i];
}
}
if (suma>0)
{
p++;
}
if(p>k)
{
odp=0;
}
if (odp!=1)
{
d=prawo;;
}
}
cout<<d;
}
0
Ja bym próbował tak:
skoro:
- na każdej półce musi leżeć co najmniej jedna książka
- książki na wejściu są już w kolejności alfabetycznej
to:
- zaczynając od ostatniej półki: wkładam jedną książkę od końca zbioru na każdą półkę
- na pierwszej półce wszystkie pozostałe
- sprawdzam minimalną długość półek dla różnych wariantów tylko dla książek które są na pierwszej półce z wyjątkiem pierwszej książki która musi na niej pozostać
Chyba najbardziej optymalnym rozwiązaniem będzie programowanie dynamiczne w tym przypadku.
0
Po pierwsze potrzebna jest tablica o wielkości N -1 reprezentująca sumy częściowe książek (suma grubości książek od pierwszej do i-tej).
Rozwiązanie leży gdzieś w ramach max(najgrubszą książka, suma grubości książek / K); (minimum), a sumą grubości wszystkich książek.
Jeśli minimum nie pasuje należy sprytnie powiększyć kandydata na nową wartość D (ja bym wybrał rozmiar najmniejszego przekroczenia zakresu, ale pewnie można wymyślić coś sprytniejszego).
0
W O(n) jesteś w stanie sprawdzić czy dla danego D zabraknie miejsca, czy nie.
Wobec tego dla najprostszego algorytmu robisz oszacowanie z dołu D jako 1, z góry jako Nmax * Dmax czyli maksymalna długość półki wg zadania i wyszukiwaniem binarnym sprawdzasz kolejne wartości D. Złożoność O(n * log(Nmax * Dmax))
Jeżeli chcesz przykładowy kod i może lepsze wytłumaczenie od mojego to rzucam ci linka do stacka gdzie masz rozwiązany analogiczny problem:
Polecam oczywiście jakąś heurystykę żeby w trochę bardziej ludzki sposób wybierać dół i górę zakresu. W gruncie rzeczy nie zmieni to złożoności, ale poprawi czas wykonania.