USACO 3.1 Humble Numbers 丑数 解题报告

从这一题开始,, 以后题目我就不贴上来了… 自己去看吧..

这一题开始肯本看不懂,, 后来是反反复复看标程看懂了..

首先要理解这么一个式子吧(算是式子吧“)

已经求出了j-1个丑数,, 现在求第j个丑数

对于每一个素数p乘以一个最小的丑数, 能使积大于第j-1个丑数

在这些乘积中寻找最小的一个即位第j个丑数.

用pindex[i]表示对于第i个素数乘以的最小丑数是多少..

/*
LANG: C
ID: zqy11001
PROG: humble
*/
#include 
#include 
#define MAX 100
#define getint(i) scanf(%d, &i)
#define insert(i) hum[count++] = i

long hum[1000001];
int pindex[MAX];
int prime[MAX];
int count;

int main(void)
{
 int k, n;
 int i;
 int min, m;
 freopen(humble.in, r, stdin);
 freopen(humble.out, w, stdout);
 getint(k);
 getint(n);
 for(i = 0; i < k; i++){
 getint(prime[i]);
 }

 insert(1);
 memset(pindex, 0, sizeof(int)*k);
 while(count <= n){
 min = 0x7FFFFFFF;
 for(i = 0; i < k; i++){
 while(prime[i] * hum[pindex[i]] <= hum[count - 1]){
 pindex[i]++;
 }

 if(prime[i] * hum[pindex[i]] < min){
 min = prime[i] * hum[pindex[i]];
 m = i;
 }
 }
 insert(min);
 }

 printf(%d\\n, hum[n]);
 return 0;
}