Разбор олимпиадной задачи — Перепись

  • В этой теме 0 ответов, 1 участник, последнее обновление 3 месяца назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6439
      @admin

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 15%):

      В доме живет N жильцов. Однажды решили провести перепись всех жильцов данного дома и составили список, в котором указали возраст и пол каждого жильца. Требуется найти номер самого старшего жителя мужского пола.

      Входные данные

      Во входном файле INPUT.TXT в первой строке задано натуральное число N – количество жильцов (N ≤ 100). В последующих N строках располагается информация о всех жильцах: каждая строка содержит два целых числа: V и S – возраст и пол человека (1 ≤ V ≤ 100, S – 0 или 1). Мужскому полу соответствует значение S=1, а женскому – S=0.

      Выходные данные

      Выходной файл OUTPUT.TXT должен содержать номер самого старшего мужчины в списке. Если таких жильцов несколько, то следует вывести наименьший номер. Если жильцов мужского пола нет, то выведите -1.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 4
      25 1
      70 1
      100 0
      3 1
      2
      2 2
      25 0
      25 1
      2

      Разбор решения задачи

      Подход к решению задачи очевиден — считываем последовательно строчки, выполняем проверку пола и сравнение возраста. Это немногим сложнее чем найти максимальное число в массиве. Тем не менее, это неплохая практика к теме «Циклы«. Простейший вариант решения может выглядеть так:

      #include <fstream>
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n;
        ifst >> n;
      
        int maxAge = 0;
        int maxPos = -1;
      
        for(int i = 0; i < n; ++i) {
          int age, sex;
          ifst >> age >> sex;
      
          if(sex == 1 && age > maxAge) {
            maxAge = age;
            maxPos = i + 1;
          }
        }
      
        ofst << maxPos;
      }
      

      Однако, на этой, как и на других олимпиадных задачах, можно хорошо попрактиковаться в использовании стандартной библиотеки. В самом деле, возможно такое решение:

      #include <fstream>
      #include <vector>
      #include <algorithm>
      
      using namespace std;
      
      struct Human {
        int age;
        bool is_man;
      };
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n;
        ifst >> n;
      
        vector<Human> people(n);
      
        for (int i = 0; i < n; ++i) {
          ifst >> people[i].age >> people[i].is_man;
        }
      
        auto oldest_it = find_if(people.begin(), people.end(), [](const Human& human) {
          return human.is_man;
        });
      
        if (oldest_it == people.end()) {
          ofst << -1;
          return 0;
        }
      
        for (auto it = people.begin(); it != people.end(); ++it) {
          if (it->is_man && it->age > oldest_it->age) {
            oldest_it = it;
          }
        }
      
        ofst << distance(people.begin(), oldest_it) + 1;
      }

      Тут мы завели структуру для хранения человека. Нам нужно вывести -1 если в векторе нет мужчин — для этого применям стандартый алгоритм find_if. Затем выполняем поиск максимума. Наконец, для поиска позиции старшего мужчины (мы ее не сохраняли) — применяется алгоритм distance. Это все хорошо, но:

      1. вместо ввода данных вручную (в цикле) можно использовать алгоритм copy — для этого нужно определить оператор потокового ввода для типа Human;
      2. вместо поиска старшего мужчины в цикле можно использовать стандартный алгоритм max_element — для этого нужно задать компаратор или определить оператор сравнения для типа Human;
      3. использовать find_if не обязательно, ведь если мы правильно описали компаратор для предыдущего пунктка — то в качестве старшегомужчины получим что-то некорректное — итератор end() или женщину;

      Записать все это можно так:

      #include <fstream>
      #include <vector>
      #include <algorithm>
      #include <iterator>
      
      using namespace std;
      
      struct Human {
        int age;
        bool is_man;
      };
      
      bool operator<(const Human& lhs, const Human& rhs) {
        if (rhs.is_man && false == lhs.is_man)
          return true;
      
        if (rhs.is_man && lhs.is_man)
          return lhs.age < rhs.age;
      
        return false;
      }
      
      istream& operator>>(istream& ist, Human& human) {
        ist >> human.age >> human.is_man;
        return ist;
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n;
        ifst >> n;
      
        vector<Human> people;
      
        copy(istream_iterator<Human>(ifst), istream_iterator<Human>(), back_inserter(people));
      
        auto oldest_it = max_element(people.begin(), people.end());
      
        if (oldest_it == people.end() || oldest_it->is_man == false)
          ofst << -1;
        else
          ofst << distance(people.begin(), oldest_it) + 1;
      }

      Это достаточно красивое решение, но, черт возьми, оно хуже самого первого в том, что содержимое файла считывается в вектор — это неэкономично. Тем не менее, лучшего решения не получится — несмотря на то, что алгоритмы типа max_element можно применять к итераторам файловых потоков:

      auto oldest_it = max_element(istream_iterator<Human>(ifst), istream_iterator<Human>());

      к таким итераторам нельзя применить алгоритм distance, а в этой задаче от нас требуют не данные старшего мужчины, а его номер…

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.