学步园

Problem Statement

　　从一串数中取数，取走其中一个数的时候，要连带取走与其相邻的数字（例如：取走10，若数串中有9和11，就也都取走）。

　　要求：给一串数，设计算法，使得取数的次数最多。

Definition

Constraints

Basic Thoughts

　　为了能让取数的次数最多，需要如下做：

　　1. 挑出没有相邻项的数字，取出它；

　　2. 挑出有一个相邻项的数字，取出它以及它的相邻项；

　　3. 绝不允许出现取出有两个相邻项的数字。

　　所以，算法判断时只有上述1,2两种可能的情况。按上述两种情况取数，直到所有数字被取完为止。

class SRMCards
{
	// basic strategy
	// 1. pick up the number which has no neighbor and remove it
	// 2. pick up the number which has one neighbor and remove them two and go back to 1
public:
	int maxTurns(vector <int> cards)
	{
		int res = 0;
		int count = cards.size();
		int len = cards.size();

		int j;
		for(j=0;j<2;j=(++j)%2)
		{
			for(int i=0;i<len;i++)
			{
				if(cards[i] != -1)
				{
					vector<int>::iterator card1 = find(cards.begin(),cards.end(),cards[i]-1);
					vector<int>::iterator card2 = find(cards.begin(),cards.end(),cards[i]+1);

					if (j == 0 && card1 == cards.end() && card2 == cards.end())
					{
						res++;
						cards[i] = -1;
						count--;
					}
					else if (j == 1 && card1 == cards.end() && card2 != cards.end())
					{
						res++;
						cards[i] = -1;
						*card2 = -1;
						count-=2;
					}
					else if (j == 1 && card2 == cards.end() && card1 != cards.end())
					{
						res++;
						cards[i] = -1;
						*card1 = -1;
						count-=2;
					}
					else continue;
				}
			}

			if (count == 0)
			{
				break;
			}
		}

		return res;
	}
};