Постановка задачи
Задача SRMCardsКратко смысл задачи такой: за один ход из вектора целых чисел изымается элемент со значением A, если в векторе есть элементы со значением A-1 или A+1, то они автоматически тоже изымаются; цель сделать как можно больше таких ходов пока вектор не опустеет.
Анализ
Рассмотрим стандартный пример, который приводится в задаче:Вектор: 11, 12, 102, 13, 100, 101, 99, 9, 8, 1. Ответ: 6
- Допустим, берем сначала 12 сразу же выпадают 11 и 13 остается 102, 100, 101, 99, 9, 8, 1
- Берем 100, и сразу же выпадают 99 и 101 остается 102, 9, 8, 1
- Берем 8, и сразу же выпадает 9 остается 102, 1
- Берем 102
- Берем 1
Решение
Идея решения такова:- отсортировать вектор по возрастанию
- после сортировки изымать самый крайний элемент слева пока вектор не опустеет
Программирование
Первый рабочий вариант решения:
#include <vector> #include <iostream> using namespace std; class SRMCards { public: SRMCards(void) {}; ~SRMCards(void) {}; int maxTurns(vector <int> cards) { int size = cards.size(); int max, t; for (int i = size-1; i >= 0; i--) { max = 0; for (int j = 1; j <= i; j++) { if (cards[j] > cards[max]) max = j; } t = cards[max]; cards[max] = cards[i]; cards[i] = t; } //for (int i = 0; i < cards.size(); i++) { // cout << cards.at(i) << endl; //} //cout << endl; int cnt = 0; while (cards.size()) { if (cards.size() > 1 && cards[0]+1 == cards[1]) { cards.erase(cards.begin()+1); } cards.erase(cards.begin()); cnt++; } return cnt; } };
Затраченное время
22.18 - 21.36 = 42 мин.Выводы
1) Cам писал алгоритм сортировки, т.е. фактически потратил время на то, что должно делаться «одной строчкой» => для сортировки векторов использовать STL.2) Когда писал алгоритм «вынимания» карт из колоды не заметил, что пытаюсь использовать элемент вектора, который предварительно удалил => операцию удаления нужно проводить после всех остальных операций.
while (cards.size()) {
cards.erase(cards.begin());
if (cards.size() > 1 && cards[0]+1 == cards[1]) {
cards.erase(cards.begin()+1);
}
cnt++;
}
Работа над ошибками
Сортировка вектора выполняется так:sort(cards.begin(), cards.end());
Окончательный вариант решения выглядит так:
#include <vector> #include <iostream> #include <algorithm> using namespace std; class SRMCards { public: SRMCards(void) {}; ~SRMCards(void) {}; int maxTurns(vector <int> cards) { sort(cards.begin(), cards.end()); int cnt = 0; while (cards.size()) { if (cards.size() > 1 && cards[0]+1 == cards[1]) { cards.erase(cards.begin()+1); } cards.erase(cards.begin()); cnt++; } return cnt; } };