USACO Section 3.1 Humble Numbers - 在朴素的算法中找到优化~我吐了...

光荣霸气的提交22次才过...并且最后AC的思路还是我要崩溃了去网上搜得别人思路...先头我用各种方法都试了..双向链表..优先队列...甚至是150多行的AVL..这题我整整用了两天..码代码超过8个小时...才通过别人的思路给AC...

那就总结一下这个AC思维...其实也是从最简单的基础上优化的..最简单的思维是当确定了K-1个数时..用这K-1个数与给出的N个素数做积~~找到比K-1这个数大的最小数..这个数就是第K个数...其实可以看出每次为了找到所需的数..会做很多前面已经做过的运算..很费时间..稍微一想...O(K*K*N)...这个复杂度真是无力吐嘈...为了利用其前面计算过的..我就用各种数据结构来存下已经计算出的数..但是效率还是很差..就算查找时间最优写得我蛋都粉了的AVL也因旋转调整过于频繁而很不理想...而AC的思维挥挥洒洒啊~~瞬间解决..根本不用什么奇怪的数据结构...就用一个数组记下这N个数每个数乘到了所构造出来有序队列的哪一位...当已经得到K-1要求K时...只要试着让N个数每个乘以下它先前已经用到的下一位..在这其中找到比K-1这个数大的最小数...然后再调整下这N个数的使用位置情况就ok了...时间复杂度瞬间降到O(K*N)..秒过数据表示鸭梨很大...

总的来说我发现了基础的算法..并也想到了不少的优化...但还是没有想到点子上...还是缺少了一种思维~~

Program:

/*  
ID: zzyzzy12  
LANG: C++  
TASK: humble
*/    
#include<iostream>    
#include<istream>
#include<stdio.h>    
#include<string.h>    
#include<math.h>    
#include<stack>
#include<algorithm>    
#include<queue> 
#define oo 2000000000
#define ll long long
using namespace std;  
ll N,K,s[101],a[100005];
priority_queue<ll> myqueue; 
ll getanswer()
{    
      ll use[101],p,i,change[101],num;
      memset(use,0,sizeof(use));  
      memset(a,0x7F,sizeof(a)); 
      p=1; a[1]=1;
      for (;p<=K;p++)
      {  
            for (i=1;i<=N;i++)
            if (a[use[i]+1]*s[i]>a[p] && a[use[i]+1]*s[i]<=a[p+1])
            {
                   if (a[use[i]+1]*s[i]<a[p+1]) num=0;                  
                   change[++num]=i;          
                   a[p+1]=a[use[i]+1]*s[i];                 
            }
            while (num) use[change[num--]]++;
      }
      return a[K+1];   
}
int main()
{
      freopen("humble.in","r",stdin);  
      freopen("humble.out","w",stdout);   
      cin>>N>>K;
      for (int i=1;i<=N;i++) cin>>s[i];  
      cout<<getanswer()<<endl;
      return 0;   
}