趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 domen111 於 2014-8-12 20:23 編輯
爬行法的題目,這題用map解應該沒錯啊! O(nlgn)為什麼會TLE?
[C++] 純文本查看 復制代碼 #include<iostream>
#include<map>
#include<climits>
#include<algorithm>
#include<set>
using namespace std;
int a[1000010];
int main()
{
int p;
cin>>p;
for(int i=0;i<p;i++)
cin>>a[i];
set<int> couse;
for(int i=0;i<p;i++)
couse.insert(a[i]);
int cc=couse.size(); //couse count
map<int,int> c;
int s=0,t=0;
int ans=INT_MAX;
while(t<=p)
{
if(c.size()>=cc)
{
ans=min(ans,t-s);
c[a[s]]--;
if(c[a[s]]==0)
c.erase(a[s]);
s++;
}
else
{
c[a[t]]++;
t++;
}
}
cout<<ans<<endl;
}
|