题目原文：http://uva.onlinejudge.org/external/1/136.html
之前的解法是逐个检查是否是Ugly Number，一直除以2,3,5直到不能整除。这样的算法算出第1500个用了20多秒的时间。
我们知道“堆”这个数据结构很特殊，他是局部有序的。堆顶始终是最小（或最大）的元素。因此，我们只需要从1开始，每次乘2,3,5的结果放入堆中，然后取出最小的数，再乘2,3,5结果放入堆中。取出的第1500个数就是结果。
这么做有一个问题，就是重复的元素会重复进入堆中。解决的办法是这次取出来的元素和上一次取出来的元素比较，如果相同的话就不计算在内。
但是在C语言中用long的话，计算到1300多的时候会溢出。。。。虽然第1500个数是没有溢出的 ，但是第1300个数乘2,3,5可能会溢出，然后放入堆中溢出的结果往往是比原来的数小，所以最后我在乘2,3,5之后判断是否比原来的数字小，如果乘2,3,5之后反而变小的话就舍弃这个结果。。。
PS：还好他只是要求1500个。所以就这么处理了。
1 #include<stdio.h> 2 long out(long r[],int s)//出堆 3 { 4 int i,j; 5 long item,x; 6 item=r[s]; 7 r[s]=r[r[0]]; 8 x=r[s]; 9 r[0]--; 10 i=s; 11 j=2*i; 12 while(j<=r[0]) 13 { 14 if(j+1<=r[0]&&r[j+1]<r[j]) j++; 15 if(x>r[j]){r[i]=r[j];i=j;j=2*i;} 16 else break; 17 } 18 r[i]=x; 19 return item; 20 } 21 void in(long r[],long item)//入堆 22 { 23 int i; 24 for(i=r[0]+1;i>1;i/=2) 25 { 26 if(item<r[i/2]) r[i]=r[i/2]; 27 else break; 28 } 29 r[i]=item; 30 r[0]++; 31 } 32 int main() 33 { 34 int j=0; 35 long r[800]={1,1},i=0,i2; 36 while(j<1500) 37 { 38 i2=i; 39 i=out(r,1); 40 if(i!=i2) 41 { 42 j++; 43 if(i<2*i) in(r,2*i); 44 if(i<3*i) in(r,3*i); 45 if(i<5*i) in(r,5*i); 46 } 47 } 48 printf("The 1500'th ugly number is %ld.\n",i); 49 return 0; 50 }