Решение задачи SRMCards с TopCoder

Постановка задачи

Задача SRMCards
Кратко смысл задачи такой: за один ход из вектора целых чисел изымается элемент со значением A, если в векторе есть элементы со значением A-1 или A+1, то они автоматически тоже изымаются; цель сделать как можно больше таких ходов пока вектор не опустеет.

Анализ

Рассмотрим стандартный пример, который приводится в задаче:
Вектор: 11, 12, 102, 13, 100, 101, 99, 9, 8, 1. Ответ: 6
  1. Допустим, берем сначала 12 сразу же выпадают 11 и 13 остается 102, 100, 101, 99, 9, 8, 1
  2. Берем 100, и сразу же выпадают 99 и 101 остается 102, 9, 8, 1
  3. Берем 8, и сразу же выпадает  9 остается 102, 1
  4. Берем 102
  5. Берем 1
Получилось пять ходов, а в ответе шесть. Делаем вывод, что если в векторе есть элементы со значениями A-1, A, A+1 то брать A “невыгодно” потому что сразу же выпадают A-1 и A+1, тем самым сокращая впоследствии число ходов. Получается, что выгодно брать элементы A-1 или A+1 (разумеется, при условии, что в векторе нет элементов со значениями A-2 или A+2 соответственно).

Решение

Идея решения такова:
  • отсортировать вектор по возрастанию
  • после сортировки изымать самый крайний элемент слева пока вектор не опустеет

Программирование

Первый рабочий вариант решения:
 
#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;
    }
};

Теги: