【例题5-7 UVA - 136】Ugly Numbers

在这里输入题意

【题解】

每个丑数x,都能生成3个丑数2x,3x,5x
则我们以1作为起点。
生成丑数。
每次取出set里面最小的那个数.
然后用它去生成其他的丑数。
加入到set里面.
然后再把set的头元素删掉就好。
取1500次.
**不知道生成的哪一个更大,那么每次取最小的就好了,set就是用来做这个事的**
**每次都取最小的来生成,那么新生成的数字,肯定也是尽可能地小的,所以不会出现取出来的不是第i小的数的情况**

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

set <ll> mset;

const ll a[] = { 2,3,5 };

int main()

{

	mset.insert(1);

	for (int i = 1; i <= 1500; i++)

	{

		ll x = (*mset.begin());

		if (i == 1500)

		{

			printf("The 1500'th ugly number is %lld.\n", x);

			break;

		}

		for (int i = 0; i < 3; i++)

		{

			ll y = x*a[i];

			mset.insert(y);

		}

		mset.erase(mset.begin());

	}

	return 0;

}

巴特西

【例题5-7 UVA - 136】Ugly Numbers

最新文章

热门文章