Матч 337, Карточный стрит (CardStraights)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

У игрока имеется набор карт. Каждая карта имеет номер от 1 до 1000000. Набор карт с последовательными номерами образуют стрит. Среди карт есть джокеры, которые могут принимать любой номер. Джокеры имеют номер 0. В задаче необходимо определить длину наибольшего стрита, который можно выложить из карт игрока.

Класс: CardStraights

Метод: int longestStraight(vector<int> cards)

Ограничения: cards содержит от 1 до 50 элементов, 0 £ cards[i] £ 1000000.

Вход. Массив целых чисел cards – значения карт игрока. Джокеры имеют номер 0.

Выход. Длина наибольшего стрита, который можно выложить из карт игрока.

Пример входа

cards

{0,6,5,10,3,0,11}

{100,100,100,101,100,99,97,103}

{0,0,0,1,2,6,8,1000}

Пример выхода

5

3

6

РЕШЕНИЕ

обработка массивов

Прочитаем во множество c значение всех карт (кроме джокеров). Таким образом избавимся от повторений значений карт. В переменной joker найдем количество джокеров. Скопируем из множества c все значения карт в исходный вектор cards.

Очевидно, что все джокеры, которые есть у игрока, следует использовать. Если вектор cards пустой, то ответом будет joker. Иначе стараемся построить самый длинный стрит начиная с i - ой карты, 0 £ i < cards.size(). Среди всех полученных стритов находим наибольший.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <set>

using namespace std;

class CardStraights

{

public:

int longestStraight(vector<int> cards)

{

set<int> c;

set<int>::iterator iter;

int joker, i, j, k, s, max;

for(max = joker = i = 0; i < cards.size(); i++)

if (!cards[i]) joker++;else c.insert(cards[i]);

for(cards.clear(), iter = c.begin(); iter != c.end(); iter++)

cards.push_back(*iter);

if (cards.empty()) max = joker;

cards.push_back(2000001);

for(i = 0; i < cards.size() - 1; i++)

{

j = s = joker; s++;

for(k = i; ; k++)

{

j -= cards[k+1] - cards[k] - 1;

if (j < 0) break;

s ++;

}

if (s > max) max = s;

}

return max;

}

};