00008 – Otwarcie nowego hipermarketu
W Bajtolandi otwarto nowy hipermarket przy skrzyżowaniu ulic szesnastej oraz sześćdziesiątej-czwartej. Z okazji tego wydarzenia zorganizowano loterię dla klientów. Przy wyjściu z hipermarketu postawiono wielką urnę. Każdy kto zrobi zakupy i wrzuci paragon do urny bierze udział w losowaniu. Każdego dnia losowane są dwa z l paragonów – ten z największą oraz najmniejszą kwotą k. Loteria trwa n dni. W loterii biorą udział wszystkie paragony znajdujące się w urnie. Każdy z paragonów może wygrać co najwyżej jeden raz.
Kierownik hipermarketu musi wiedzieć ile wyda na loterię zakładając, że wygrywa właściciel paragonu z najwyższą kwotą a nagrodą jest różnica pomiędzy wartością na jego paragonie a najniższą kwotą.
n ⩽ 105
1 ⩽ k ⩽ 109
Input:
5
3 1 2 3
2 1 1
4 10 5 5 1
0
Output:
12
Kod źródłowy w C++:
#include <bits/stdc++.h> using namespace std; map<int, int> coupons; int main() { int n, l, k, sum = 0; cin >> n; for (int i = 0; i < n; i++) { cin >> l; for (int j = 0; j < l; j++) { cin >> k; auto ite = coupons.find(k); if (ite == coupons.end()) { coupons.insert(make_pair(k, 1)); } else { ite->second++; } } auto last = coupons.end(); auto first = coupons.begin(); last--; sum += last->first - first->first; last->second--; first->second--; if(last->second < 1) { coupons.erase(last); } if(first->second < 1) { coupons.erase(first); } } cerr << sum; }