pku 1338 紧密数.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
using namespace std;

//PKU 1338 Ugly Numbers
/*
输入：
1
10
500

输出：
1
12
937500

说明：
同样是蛮力法，但是用列举每个数再判断的方法一定会超时，何不直接构造这个序列呢？
*/
#define NMAX 1505
#define MAX 99999999
int ji[3]={2,3,5};
long a[NMAX];

void cal()
{
	int where[3],k,min;//where[]使a[where[i]]*ji[i]刚好大于当前a[]已知序列的最大值
	a[1]=1;a[2]=2;a[3]=3;a[4]=4;a[5]=5;a[6]=6;
	where[0]=3;where[1]=3;where[2]=1;
	for(k=5;k<NMAX-1;k++)
	{
		min=MAX;
		//如果a[where[i]]*ji[i]不大于已知序列的最大值，让作为a[]数组下标的where[i]加1
		while(a[where[0]]*ji[0]<=a[k]) where[0]++;
		while(a[where[1]]*ji[1]<=a[k]) where[1]++;
		while(a[where[2]]*ji[2]<=a[k]) where[2]++;
		if(a[where[0]]*ji[0]>a[where[1]]*ji[1]) 
		min=a[where[1]]*ji[1];
		else 
		min=a[where[0]]*ji[0];
		if(min>a[where[2]]*ji[2]) 
		min=a[where[2]]*ji[2];
		a[k+1]=min;//将a[where[0]]*ji[0]，a[where[1]]*ji[1]，a[where[2]]*ji[2]的最小值加入序列
	}	
}

int main()
{
	int shuru;
	cal();
	while(1)
	{
		scanf("%d",&shuru);
		if(shuru==0) break;
		else cout<<a[shuru]<<endl;
	}
	return 0;
}