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;
}