ztrlovesluckynumbers(STL)

ztr喜欢幸运数字，他对于幸运数字有两个要求
1：十进制表示法下只包含4、7
2：十进制表示法下4和7的数量相等
比如47,474477就是
而4,744,467则不是

现在ztr想知道最小的但不小于n的幸运数字是多少

输入描述

成都创新互联公司-专业网站定制、快速模板网站建设、高性价比黑山网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式黑山网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖黑山地区。费用合理售后完善，十多年实体公司更值得信赖。

有T(1≤n≤105)组数据，每组数据一个正整数n(1≤n≤1018)

输出描述

有T行，每行即答案

输入样例

2
4500
47

输出样例

4747
47

Hint

请尽可能地优化算法，考虑全面

LuckNum.h
#include 

class LuckNum
{
public:
	int minnum(int n)
	{
		if (n < 47)
			n = 47;
		int tmp = n;
		for (int i = tmp;; i++){
			int array[2] = { 0 };
			tmp = i;
			while (tmp != 0){
				if (tmp % 10 == 4 ){
					array[0]++;
				}
				else if (tmp % 10 == 7){
					array[1]++;
				}
				else
					break;
				tmp /= 10;
			}
			if (tmp == 0){
				if ( array[0] == array[1] )
					return i;
			}
		}
	}
};
Test.cpp
#define _CRT_SECURE_NO_WARNINGS

#include "LuckNum.h"
using namespace std;

int main()
{
	int l = 0;
	scanf("%d", &l);
	while (l<1 || l>100000){
		return -1;
	}
	int *a = new int [l];
	for (int i = 0; i < l; ++i){
		int n = 0;
		scanf("%d", &n);
		a[i] = n;
	}
	LuckNum l1;
	for (int i = 0; i < l; ++i){
		cout << l1.minnum(a[i]) << endl;
	}

	system("pause");
	return 0;
}

运行结果:

可看出运行结果正确，但是for循环中i++似乎不太合理（如下：）

47 74

4477 4747 4774 7447 7474 7744

444777 447477 447747 447774 474774 。。。

所以把i每次加一是不合理的，我们可以进行优化

#include 
#include 
#include 
using namespace std;

class LuckNum
{
public:
	int minnum(int n)
	{
		if (n < 47)
			n = 47;
		vector a;
		a.push_back(4);
		a.push_back(7);
		while(1){
			sort(a.begin(),a.end());
			while (1){
				int ret = a[0];
				for (int i = 1; i < a.size(); ++i){
					ret =ret * 10 + a[i];
				}
				if (ret >= n){
					return ret;
				}
				if (false == next_permutation(a.begin(), a.end()))
					break;
			}
			a.push_back(4);
			a.push_back(7);
		}
	}
};

运行结果：

我们用到了STL中的next_permutation(),与之对应的还有一个prev_permutation(),

它们都在#include 中包含

分享名称：ztrlovesluckynumbers(STL)
文章转载：http://shouzuofang.com/article/pjspsh.html