Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- //WORKS!!!
- using std::cin;
- using std::cout;
- using std::vector;
- using std::endl;
- using std::swap;
- struct Customer {
- int start_time;
- int end_time;
- int ads_showed;
- Customer();
- Customer(int beg, int end);
- };
- Customer::Customer() { }
- Customer::Customer(int beg, int end) {
- start_time = beg;
- end_time = end;
- ads_showed = 0;
- }
- //сравнение
- bool isBigger(Customer L, Customer R) {
- if (L.end_time > R.end_time) {
- return true;
- } else if (L.end_time == R.end_time) {
- return L.start_time > R.start_time;
- } else {
- return false;
- }
- }
- //HEAP
- class Heap {
- public:
- Heap();
- ~Heap();
- void push(Customer val);
- void adUpdater(unsigned long start_index, unsigned long adTime); //обновить элементы кучи при добавлении нового показа рекламы
- void siftDown(unsigned long index, unsigned long heap_size);
- void heapSort();
- void buildHeap();
- unsigned getMinAdsCount(); //получить минимальное кол-во рекламы
- private:
- vector<Customer> buffer;
- };
- Heap::Heap() { }
- Heap::~Heap() {
- buffer.empty();
- }
- void Heap::push(Customer val){
- buffer.push_back(val);
- }
- void Heap::buildHeap()
- {
- for (long i = buffer.size() / 2 - 1; i >= 0; --i) {
- siftDown(buffer.size(), i);
- }
- }
- void Heap::siftDown(unsigned long heapSize, unsigned long i )
- {
- unsigned long left = 2 * i + 1;
- unsigned long right, largest;
- while (left < heapSize) {
- right = left + 1;
- largest = i;
- if(isBigger(buffer[left], buffer[i])) {
- largest = left;
- }
- if(right < heapSize && isBigger(buffer[right], buffer[largest])) {
- largest = right;
- }
- if( largest != i ) {
- swap(buffer[i], buffer[largest]);
- i = largest;
- left = 2 * i + 1;
- } else {
- return;
- }
- }
- }
- void Heap::heapSort() {
- for (unsigned long i = buffer.size() - 1; i > 0; --i) {
- swap(buffer[0], buffer[i]);
- siftDown(i, 0);
- }
- }
- void Heap::adUpdater(unsigned long start_index, unsigned long adTime) {
- for (unsigned long i = start_index; i < buffer.size(); ++i) {
- if(buffer[i].start_time <= adTime && buffer[i].end_time >= adTime) {
- ++(buffer[i].ads_showed);
- }
- }
- }
- unsigned Heap::getMinAdsCount() {
- unsigned ads = 0;
- for (int i = 0; i < buffer.size(); ++i){
- if (buffer[i].ads_showed == 0) {
- adUpdater(i, buffer[i].end_time - 1);
- ++ads;
- }
- if (buffer[i].ads_showed == 1) {
- adUpdater(i, buffer[i].end_time);
- ++ads;
- }
- }
- return ads;
- }
- // MAIN
- int main() {
- unsigned n;
- cin >> n;
- Heap heap;
- for(unsigned i = 0; i < n; ++i) {
- int start, end;
- cin >> start >> end;
- heap.push(Customer(start, end));
- }
- heap.buildHeap();
- heap.heapSort();
- cout << heap.getMinAdsCount();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement