Omówienie zadania “Wizyta”

Szczegółowe omówienie zadania Wizyta:
https://youtu.be/LryJ-4lrXts?t=1431

Zadanie przygotowuje do Olimpiady Informatycznej.
Ćwiczy Binary Search, Sumy Prefiksowe, manipulowanie tablicami
Poniżej kod wzorcowy do zadania użyty w powyższym omówieniu:

#include <bits/stdc++.h>
using namespace std;

const int MAX_CIASTEK = 2e5+7;

int rodzaje_ciastek[MAX_CIASTEK];
int ile_ciastek_rodzaju[MAX_CIASTEK];
int ciastka[MAX_CIASTEK];
long long int sumy_prefiksowe[MAX_CIASTEK];

bool PosortujCiastkaMalejaco (int wartosc1, int wartosc2) {
if (wartosc1 > wartosc2) {
return true;
}
return false;
}

int BinarySearchLewy (int poczatek, int koniec, long long int wartosc) {
int srodek;
while (poczatek < koniec) {
srodek = (poczatek + koniec) / 2;
if (sumy_prefiksowe[srodek] >= wartosc)
koniec = srodek;
else
poczatek = srodek + 1;
}
return poczatek;
}

int main ( ) {

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int ile_rodzajow, ile_ciastek, ile_pytan;
int ile_musi_zjesc;
long long int pytanie;
int i, j;

cin >> ile_rodzajow;
for (i=0; i<ile_rodzajow; ++i) {
cin >> rodzaje_ciastek[i];
}
for (i=0; i<ile_rodzajow; ++i) {
cin >> ile_ciastek_rodzaju[i];
}

ile_ciastek=0;
for (i=0; i<ile_rodzajow; ++i) {
for (j=0; j<ile_ciastek_rodzaju[i]; ++j) {
ciastka[ile_ciastek] = rodzaje_ciastek[i];
++ile_ciastek;
}
}

sort (ciastka, ciastka+ile_ciastek, PosortujCiastkaMalejaco);

sumy_prefiksowe[0] = ciastka[0];
for (i=1; i<ile_ciastek; ++i) {
sumy_prefiksowe[i] = sumy_prefiksowe[i-1] + ciastka[i];
}

cin >> ile_pytan;
for (i=0; i<ile_pytan; ++i) {
cin >> pytanie;
ile_musi_zjesc = BinarySearchLewy (0, ile_ciastek-1, pytanie);
++ile_musi_zjesc;
cout << ile_musi_zjesc << “\n”;
}

return 0;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz