题意：1000个元素，每个元素的大小-1e9<=a[i]<=1e9，然后让你重新安排这些元素的位置
获得最长的前缀斐波那契数列
分析：枚举第一个元素和第二个元素，因为在题目元素的范围内，最多形成长度为90的斐波那契数列
除非有全0的情况出现，这种情况会达到长度1000
所以这种情况特判一下（记录一下零元素的个数就行了）
然后枚举是n^2的
找元素是90，然后找的时候，我用的map来找
所以时间复杂度是略大是O（90n^2logn）
所以由于不可能每次都找到90，所以均摊比较小，这题时限是3s，我跑了2012ms
主要是我太弱（这是刚比完赛看题解写的）
#include <cstdio> #include <iostream> #include <cstring> #include <cstdlib> #include <vector> #include <string> #include <algorithm> #include <map> using namespace std; typedef long long LL; const int N=1000000+5; map<LL,int>mp; LL a[1005]; int main() { int n; LL res=0,mx=-1; scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%I64d",&a[i]); mx=max(a[i],mx); if(a[i]==0)++res; mp[a[i]]++; } LL ans=2; for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { if(j==i)continue; if(a[i]==0&&a[j]==0)continue; LL x=a[i],y=a[j],cnt=2; vector<LL>t; t.clear(); t.push_back(x); t.push_back(y); mp[x]--; mp[y]--; while(x+y<=mx&&mp[x+y]>0) { LL tmp=x+y; mp[tmp]--; t.push_back(tmp); x=y; y=tmp; ++cnt; } for(int k=0;k<t.size();k++) mp[t[k]]++; ans=max(ans,cnt); } } printf("%I64d ",max(ans,res)); return 0; }
然后后来我又写了一份，之所以用MAP找，是因为元素范围大
所以可以用排序hash，用lower_bound来找，这样复杂度其实和上面的复杂度原理上和上面一样
但是由于用数组实现，所肯定比STL要快，写成这样才跑了826ms
所以说能不用STL，还是不用吧
#include <cstdio> #include <iostream> #include <cstring> #include <cstdlib> #include <vector> #include <string> #include <algorithm> #include <map> using namespace std; typedef long long LL; const int N=1000000+5; int a[1005],b[1005],sum[1005],pos[1005]; int main() { int res=0,mx=-1,n,l=0; scanf("%d",&n); for(int i=1; i<=n; ++i) { scanf("%d",&a[i]); mx=max(a[i],mx); if(a[i]==0)++res; } sort(a+1,a+1+n); b[++l]=a[1]; for(int i=2; i<=n; ++i) if(a[i]!=a[i-1])b[++l]=a[i]; for(int i=1; i<=n; ++i) { pos[i]=lower_bound(b+1,b+1+l,a[i])-b; ++sum[pos[i]]; } int ans=2; for(int i=1; i<=n; ++i) { for(int j=1; j<=n; ++j) { if(j==i)continue; if(a[i]==0&&a[j]==0)continue; int x=a[i],y=a[j],cnt=2; vector<int>t; t.clear(); sum[pos[i]]--; sum[pos[j]]--; t.push_back(pos[i]); t.push_back(pos[j]); while(x+y<=mx) { int z=lower_bound(b+1,b+1+l,x+y)-b; if(z==l+1||b[z]!=x+y||!sum[z])break; sum[z]--; t.push_back(z); int tmp=x+y; x=y; y=tmp; ++cnt; } for(int k=0; k<t.size(); k++) sum[t[k]]++; ans=max(ans,cnt); } } printf("%d ",max(ans,res)); return 0; }