Omówienie zadania “Kreatywna Księgowość”

Omówienie zadania “Kreatywna Księgowość”

Szczegółowe omówienie zadania Kreatywna Księgowość:

https://youtu.be/ysWHtsT96e0?t=1920

Zadanie pochodzi  z obozu ONTAK 2010:

W rozwiązaniu użyto struktury / typu “set” języka C++który jest szczegółowo wyjaśniony w poniższym fragmencie:

https://youtu.be/ysWHtsT96e0?t=8013

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

const int MAX_DNI = 2e5+7;
long long int sum_pref_modulo[MAX_DNI];
set reszty;

int main() {
 int liczba_dni;
 long long int liczba_uczestnikow;
 long long int akt_reszta, max_reszta;
 long long int wydatek;
 set::iterator it;
 int i;

 cin >> liczba_dni;
 cin >> liczba_uczestnikow;
 
 for (i=1; i<=liczba_dni; ++i) { cin >> wydatek;
	sum_pref_modulo[i] = (sum_pref_modulo[i-1]+wydatek) % liczba_uczestnikow;
	sum_pref_modulo[i] = (sum_pref_modulo[i]+liczba_uczestnikow) % liczba_uczestnikow;
 }

 reszty.insert(0);
 max_reszta=0;
 for (i=1; i<=liczba_dni; ++i) {
    it = reszty.upper_bound(sum_pref_modulo[i]);
	if ( it != reszty.end() ) {
	   akt_reszta = liczba_uczestnikow - ((*it)-sum_pref_modulo[i]);
	   max_reszta = max (max_reszta, akt_reszta);
  	}  
	akt_reszta = sum_pref_modulo[i];
	max_reszta = max (max_reszta, akt_reszta);
   	reszty.insert(sum_pref_modulo[i]);
 }

 cout << max_reszta << "\n";
 return 0;
}


Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz