priority_que part2 - DL Руководство пользователя

2013\December\Silver\1 - "MSCHED"http://dl.gsu.by/task.jsp?nid=1239290&cid=130

Идея решения - жадный алгоритм.
Сортируем коров по возрастанию дня дед-лайна.
Устанавливаем время на Конец.
Пока время>0
Выбираем максимальный надой из коров, для которых ещё не наступил дед-лайн
Прибавляем его к ответу
Декрементируем время

Основные использованные конструкции связанные с priority_que

struct cow {
             int g, d;
             // Эта функция сравнения, которая будет использована для сравнения cow
             // при загрузке в priority_que
             bool operator< (cow const& c) const
               {
                 return g < c.g;
               }
            };

priority_queue<cow> q;    // объявление q
q.push(cows[curcow]);     // добавление в q
if (q.size() > 0)         // проверка на пустоту - аналог not q.empty()
total += q.top().g;       // добавить к ответу поле g элемента в вершине
q.pop();                  // удалить элемент в вершине (наибольший)

Полный комментированный текст решения приведен далее

all.cpp

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

#define N_MAX 10000

struct cow {
             int g, d;
             // Эта функция сравнения, которая будет использована для сравнения cow
             // при загрузке в priority_que
             bool operator<(cow const& c) const
               {
                 return g < c.g;
               }
            };
cow cows[N_MAX];

// Эта функция сравнения используется в сортировке по убыванию d
inline bool sort_by_d(cow const& a, cow const& b)
  {
	return a.d > b.d;
  }

int main()
{
  freopen("msched.in", "r", stdin);
  freopen("msched.out", "w", stdout);
  int n;
  cin>> n;
   for (int i = 0; i < n; i++)
     {
       cin >> cows[i].g;
       cin >> cows[i].d;
     }
  sort(cows, cows + n, sort_by_d);
  int total = 0;            // Ответ
  priority_queue<cow> q;    // Хранит, коров которых уже можно доить
  int curcow = 0;           // Индекс следующей коровы, которая станет доступна
                            // при уменьшении t
  for (int t = N_MAX; t >= 1; t--)
    {                       // Находим и заносим в q всех коров, которых можно доить
                            // в момент t
       while (curcow < n && t <= cows[curcow].d)
         {
           q.push(cows[curcow]);
           curcow++;
         }
		// Если есть доступная корова
		// забираем с максимальным надоем, добавляем к ответу
       if (q.size() > 0)
         {
           total += q.top().g;
           q.pop();
         }
    }
  cout << total;
}

Текст решения без комментариев

withoutcomment.cpp

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

#define N_MAX 10000

struct cow {
             int g, d;
             bool operator<(cow const& c) const
               {
                 return g < c.g;
               }
            };
cow cows[N_MAX];

inline bool sort_by_d(cow const& a, cow const& b)
  {
	return a.d > b.d;
  }

int main()
{
  freopen("msched.in", "r", stdin);
  freopen("msched.out", "w", stdout);
  int n;
  cin>> n;
   for (int i = 0; i < n; i++)
     {
       cin >> cows[i].g;
       cin >> cows[i].d;
     }
  sort(cows, cows + n, sort_by_d);
  int total = 0;
  priority_queue<cow> q;
  int curcow = 0;
  for (int t = N_MAX; t >= 1; t--)
    {
       while (curcow < n && t <= cows[curcow].d)
         {
           q.push(cows[curcow]);
           curcow++;
         }
       if (q.size() > 0)
         {
           total += q.top().g;
           q.pop();
         }
    }
  cout << total;
}