fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. // kolejka priorytetowa odwrotna tzn. minimalny koszt biletu  na topie (koszt * -1)
  5. // w kolejce zapamiertuje dla kazdej kasy:   koszt,   ile biletów max biletów mozna kupic
  6. // zaczynam od konca trasy i kupuje bilety które mogłem kupic wczesniej od najtanszych zgodnie z kosztem w kolejce, jednak nie kupuje wiecej niz potrzebuje
  7.  
  8.  
  9. priority_queue< pair<int, int> > q; // kolejna 2  elementów: koszt najmniejszy,  ile biletów max biletów mozna kupic
  10.  
  11. int const max_tab = 1000001;
  12.  
  13.  
  14. int main() {
  15.  
  16.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  17.  
  18. 	int n;
  19. 	long long wynik = 0;
  20. 	int ile_kupilem = 0; // ile kupiłem biletów w kasie do tej pory 
  21.  
  22. 	cin >> n;
  23. 	// wszystkie kasy do kolejki (kolejka typu min, czyli koszt * -1)
  24. 	for (int i = 0; i < n; ++i) {
  25. 		int koszt, licza_bil;
  26. 		int nr_kasy = i+1;
  27. 		cin >> koszt >> licza_bil;
  28. 		q.push(make_pair(koszt*(-1), licza_bil));
  29. 	}
  30.  
  31. 	// zaczynam od konca trasy i kupuje bilety które mogłem kupic wczesniej od najtanszych zgodnie z kosztem w kolejce 
  32. 	for (int i = n+1; i>0; --i) { 
  33. 		pair <int, int> aktualna_kasa = q.top();
  34. 		int koszt = aktualna_kasa.first;
  35. 		int licza_bil = aktualna_kasa.second;
  36. 		int ile_kupic = min(licza_bil,n-ile_kupilem); // tyle najwiecej mógłbym kupic od danej kasy do konca trasy,  jednak nie więcej niz  jest w danej kasie  (liczba_bil)
  37. 		ile_kupilem += ile_kupic;
  38. 		wynik += ile_kupic * koszt; // na końcu zmienię -1
  39. 		q.pop(); //usuwam kase z gory kolejki więcej biletów w tej kasie nie mogę kupić
  40. 		cout << " ile_kupic: "<< ile_kupic <<"  koszt: " << wynik << endl;
  41. 		if (ile_kupilem>=n) {
  42. 			break;
  43. 		}
  44. 	}
  45. 	wynik=wynik*(-1);
  46. 	cout << wynik;
  47. 	return 0;
  48. }
  49.  
Success #stdin #stdout 0.01s 5456KB
comments (?)
stdin
copy 
4
2 1
5 5
100 100
1 5
stdout
copy 
 ile_kupic: 4  koszt: -4
4
https://ideone.com/a4MocJ
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!