[POJ 3320][雙指針] Jessica's Reading Problem

原題連結

對於單調隊列、序列單調性不再多做討論，可以先做這題。

一樣的，雙指針的算法(幾乎所有)基於此性質：

滿足L的最小的R若是R0，則滿足L+1的最小的R必定>=R0

在啟用雙指針算法之前不妨多確認一下是否滿足此性質，不然可能會WA到快瘋掉(個人經驗)。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1000000+5;
const int INF=(1<<30);
vector<int> disc;
int a[maxn],show[maxn];
void add(int x,int& cnt)
{
    a[x]=lower_bound(disc.begin(),disc.end(),a[x])-disc.begin();
    if(!show[a[x]]) cnt++;
    show[a[x]]++;
}
void sub(int x,int& cnt)
{
    show[a[x]]--;
    if(!show[a[x]]) cnt--;
}
int main()
{
    int P;
    scanf("%d",&P);
    for(int i=0;i<P;i++) {scanf("%d",a+i);disc.push_back(a[i]);}
    sort(disc.begin(),disc.end());
    disc.resize(unique(disc.begin(),disc.end())-disc.begin());
    int ans=INF,cnt=0;
    for(int L=0,R=-1;L<P;sub(L++,cnt))
    {
        while(cnt<disc.size() && R+1<P) add(++R,cnt);
        if(cnt<disc.size()) break;
        ans=min(ans,R-L+1);
    }
    printf("%d\n",ans);
}