POJ 1003 解题报告 Hangover

简单题。

注意不要重复计算。

使用二分查找的思想。

AC。

#include <iostream>
#include <map>

using namespace std;

int getCards(map<int, double>&, double);
int binaryChop(map<int, double>&, double, int, int);

int main ()
{
	double dLength;

	map<int, double> mStdLength;

	mStdLength[0] = 0;

	while ( cin >> dLength )
	{
		if (dLength == 0.0)
		{
			break;
		}

		cout << getCards(mStdLength, dLength) << " card(s)" << endl;
	}

	return 0;
}

int getCards(map<int, double>& mStdLength, double dLength)
{
	map<int, double>::iterator iterm = mStdLength.end();
	if (dLength > (--iterm)->second)
	{
		int i = iterm->first;
		while (1)
		{
			mStdLength[i + 1] = mStdLength[i] + 1.0 / (i + 2);
			if (dLength <= mStdLength[i + 1])
			{
				return i + 1;
			}
			else {
				i++;
			}
		}
	}
	else
	{
		int i = iterm->first;
		binaryChop(mStdLength, dLength, 0, i);
	}
}

int binaryChop(map<int, double>& mStdLength, double dLength, int iFirst, int iLast)
{
	if (iFirst + 1 == iLast)
	{
		return iLast;
	}

	int iMid = (iFirst + iLast)/2;

	if (dLength <= mStdLength[iMid])
	{
		binaryChop(mStdLength, dLength, iFirst, iMid);
	}
	else if (dLength > mStdLength[iMid])
	{
		binaryChop(mStdLength, dLength, iMid, iLast);
	}
}