[C++]XI OI - problem z kodem

Robie to zadanie http://main.edu.pl/user.phtml?op=showtask&task=prz&con=OI11
Algorytm mam już wymyslony i wydaje się poprawny, problem z kodowaniem...
Nie wiem zupełnie co poprawić aby otrzymać dobry wynik, choc wszystko pisze zgodnie ze swoim pomysłem.
Otóż, algorytm ma ze zbioru oczekujacych bajtołazów wybierac po kolei tych, którzy mogą przejsc na druga strone. Wybranych wrzucam do tablicy tab2. Jesli ob_waga, czyli waga tych na moscie jest wieksza od obciazenia wtedy przeszukuje tablice tab2 aby znalezc najwolniejszego (czyli tego, który bedzie miał najwiekszy czas). Kiedy go znajde, dodaje wynik do sumy (sumuje wszystkich najwolniejszych), czyszcze tab2 i rozpoczynam poszukiwania nastepnej grupy od miejsca w ktorym poprzednio skonczylem w tab.
Pytanie tylko, gdzie moge robic bład, sprawdzałem większość możliwości, ale żadna nie chce działać

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
using namespace std;

int main(){
    int n,ob,czas,waga,suma=0,max=0,ob_waga=0,max_czas=0;
    vector<pair<int,int> >tab;
    vector<pair<int,int> >::iterator it;
    vector<pair<int,int> >tab2;
    vector<pair<int,int> >::iterator it2;

    cin>>ob>>n;
    for(int i=0;i<n;++i){
        cin>>czas>>waga;
        tab.push_back(make_pair(waga,czas));  //tablica grupy oczekujacej
        sort(tab.begin(),tab.end());

    for(it=tab.begin();it!=tab.end();++it){
        if(ob_waga+it->first < ob){
            tab2.push_back(make_pair(it->first,it->second)); //tablica tych na moscie
            ob_waga+=it->first; //waga kolejnego dodana do wagi wszystkich na moscie

            if(ob_waga+it->first > ob){
                for(it2=tab2.begin();it2!=tab2.end();++it2){
                    if(it2->second > max_czas) max_czas=it2->second;
                }
                suma+=max_czas;
                tab2.clear();
                ob_waga=0; //zaczynam nowe poszukiwanie w pozostalej grupie, wiec waga mostu=0;
            }

        }
      }
    }
    cout<<suma<<endl;



}

Ale ten twój kod nie przechodzi nawet testowego przypadku, wiec o czym tu w ogóle rozmawiać? ;]
Poza tym nie bardzo rozumiem czemu wszystkie operacje wykonujesz w pętli która powinna tylko wczytać wejscie...
Ja to widzę tak:

• czytasz wejście
• sortujesz malejąco po czasie

• dopóki są jeszcze jakieś bajtołazy
  • wybierasz najwolniejszych i montujesz z nich grupę (tzn przeglądasz tablicę i szukasz takich którzy są wolni, ale nie za ciężcy)
  • grupę usuwasz z tablicy

Wiem, że daje zły wynik bo problem tkwi w moim "kalectwie" (czyt. Nie umiem napisać tego co myśle)...

Ja to widzę tak:

• podaj wagi i czasy oczekujacych
• posortuj od najlzejszego (wiecej wtedy moze ich wejsc na most)
• dla wszystkich dodanych sprawdz:
  • jesli waga pierwszego < obciazenia mostu - wsadz go na most
  • z nastepnymi podobnie
  • kiedy waga bajtołazów na moscie >= obciazeniu
  • wyznacz najwolniejszego z nich i dodaj jego czas do sumy czasów najwolniejszych
  • przepusc grupe przez most (tab2.clear())
• dla pozostałych postepuj tak samo az wszyscy przejda przez most

To chciałem wcielic w program, ale zupelnie nie wiem gdzie popełniam błąd - robie wszystko tak jak myślę.
Co o tym sądzisz/sądzicie i co mozna poprawić.

Raz że masz po prostu błąd w obliczaniu tego. Dwa, nie ma sensu tego poprawiać bo algorytm jest błędny. Kontrprzykład:
obciążenie mostu = 10
waga czas
1 10
9 1
9 10
1 1
Twój pomysł to posortować to tak (od najmniejszej wagi):
1 10
1 1
9 1
9 10
A następnie wybierasz sobie grupę:
1 10
1 1
I tyle, bo żadna 9 juz tam nie wejdzie. Czas przejścia tej grupy to 10
Kolejna grupa:
9 1
Czas przejścia to 1
Kolejna grupa
9 10
Czas przejścia to 10
W sumie wg twojego algorytmu mamy czas przejścia 21

Wg mojego algorytmu sortujemy tak (od najwiekszego czasu, zeby powolnych upychać razem, bo i tak liczy sie czas najwolniejszego w grupie)
1 10
9 10
9 1
1 1
Pierwsza grupa to:
1 10
9 10
Czas przejścia 10
Druga grupa to
9 1
1 1
Czas przejscia to 1
W sumie czas łaczny to 11

Napisałem fragment tego Twojego algorytmu, jednak wynik daje 24 - tak jakby petla sie obracała tylko raz i nie dodawała więcej

for(it=tab.begin();it!=tab.end();++it){
        while(ob_waga<ob){
            if(it->first > max_czas) max_czas+=it->first;
            ob_waga+=it->second;
        }
    }
        tab.erase(tab.begin()+licznik);
        ++licznik; //oddalenie w tablicy

licznik jest po to aby móc usunąc konkretny element.
Małe zmiany to it->first - czas, it->second - waga.

Bo musisz puścić to wszystko w jeszcze jednej pętli
while(mamy coś w tablicy)
!
Ale nadal widzę tam jakieś cuda na kiju. Miałeś posortować po czasie malejąco, więc nie musisz sprawdzać żadnego warunku z czasem. Powinieneś tam mieć

while(tablica nie jest pusta)
{
  pozostala_waga = max_obciazenie_mostu; //za każdym razem musisz mieć tą wartość ustawioną od nowa!
  suma_czasu = suma_czasu + tablica.begin()->czas; //bo przecież najwolniejszy będzie na początku tablicy zawsze i on zawsze przejdzie!
  for(po tablicy) //formujemy drużynę do przejścia
  {
    if(it->waga < pozostala_waga) //mozemy dorzucić kogoś na most
    {
      pozostala_waga = pozostala_waga - it->waga; //dorzucamy
      kasujemy go z tablicy
    }
  }
}

W tym momencie wyrzuca mi błąd

 while(!tab.empty()){
        ob_waga=ob;
        suma=suma+it->first;
        for(it=tab.begin();it!=tab.end();++it){
            if(it->second < ob_waga){
                ob_waga=ob_waga-it->second;
                tab.erase(tab.begin());
                
            }
        }

Mam to napisać za ciebie?

suma=suma+it->first;

?
Skad wiesz na co wskazuje tutaj it? tym bardziej przy 1 obiegu pętli? Powinieś tu mieć po prostu tab.begin()
Poza tym obawiam się ze operacja erase() może "zepsuć" iterator, bo modyfikuje tablicę.
Warunek w if() powinien byc <=
Poza tym "wyrzuca mi błąd" niewiele mówi...
Erasowanie tab.begin() jest jeszcze gorsze niż to co miałeś, bo nie zawsze bierzesz elementy po kolei od przodu. Chyba nie kminisz tego algorytmu...
Przykład:
w c
9 10
8 10
1 5
dla maksymalnej wagi = 10

1. Sortujemy malejąco po czasie
   w c
   9 10
   8 10
   1 5
2. Tablica nie jest pusta -> formujemy pierwszą drużynę:
   bierzemy 9 10 z początku, usuwamy je z tablicy
   suma czasu w tym kroku = 10
   następne 8 10 nam nie pasuje bo jest za cięzkie, wiec idziemy dalej
   bierzemy 1 5 bo wagowo nam jeszcze pasuje, usuwamy je z tablicy (zauważ że to nie jest element tab.begin() ! tylko element kolejny!)
3. Tablica nie jest pusta -> formujemy drugą drużynę
   bierzemy 8 10 i usuwamy z tablicy
   suma czasu = 10 + 10 = 20
4. Tablica jest pusta, wypisujemy wynik

Więc tak

suma+=tab.begin();

Błąd: no match for 'operator+=' in 'suma += (&tab)->std::vector<_Tp, _Alloc>::begin with _Tp = std::pair<int, int>, _Alloc = std::allocator<std::pair<int, int> >'|

Co do tab.erase(), to z vectora inaczej sie usuwac chyba nie da (?) Ewentualnie swap z tab.back(), ale nie wiem czy to przy parach zadziała.

Kminie algorytm, rozumiem co piszesz, ale nie umiem go napisać i to jest najgorsze...

Chłopie MYŚL!
Masz wektor PAR, jak byk napisałem ci wcześniej tablica.begin()->czas;
Niewyraźnie napisałem?
No to już sobie sam musisz wymyślić jak bezpiecznie usuwać. Możliwe że to nic nie zepsuje i będzie działać ok, ale mam wątpliwości. Możesz od biedy napisać po prostu własną listę i własną klasę do obsługi tyc danych i korzystać z tego a nie z vector i pair. To raptem 3min pisania...