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