Poj 3320 Jessica's Reading Problem(尺取法)
2630 ワード
アドレス:http://poj.org/problem?id=3320 标题:尺取に関する2番目の例題に挑戦する.初めて書くのがタイムアウトになりましたが、後で答えと比較すると、stlの関数を頻繁に呼び出してタイムアウトしたのかもしれません.テーマは水ですが、stlを呼び出す関数を少なくすることができることを学びました.できるだけ少なくして、使っているうちに時間をつぶさないでください.次はacコードです.
#include
#include
#include
using namespace std;
const int maxn=1e6+5;
int a[maxn];
int Count=0;
int main()
{
map<int,int>mp;
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
if(mp[a[i]]==0) Count++;
mp[a[i]]++;
}
int ans=0;
mp.clear();
int res=n+1;
int k=1;
int i=1;
while(1)
{
while(i<=n&&ansif(mp[a[i]]==0) ans++;
mp[a[i++]]++;
}
if(ansbreak;
res=min(res,i-k);
mp[a[k]]--;
if(mp[a[k]]==0) ans--;
k++;
}
printf("%d
",res);
return 0;
}