[ZOJ 3297 Cookie Choice II]头尾指针维护

【题目大意】

就是找一个最短连续子序列，使得对于每个i,min[i]<=sum(i)<=max[i]

【算法分析】

很简单的头尾指针维护。

不过要注意题目有负数等无关数字，无视即可（只增加长度）。

然后由于满足单调性我们维护一个最短的区间使得其满足所有的min

然后判断这时候符不符合max即可。

【其它】比赛时1A

【CODE】

#include #include int n,kind,ans;
int hash[3000],a[401111],min[3000],max[3000];

void work(){
    ans=0x7FFFFFFF;
    int i,j=0,que=0,more=0;
    for (i=1;i<=kind;i++){
      if (min[i]>0) que++;
      if (max[i]<0) more++;
    }   
    for (i=1;i<=n;i++){
        while (j            j++;
            if (a[j]>=1 && a[j]<=kind){
              hash[a[j]]++;
              if (hash[a[j]]==max[a[j]]+1) more++;
              if (hash[a[j]]==min[a[j]]) que–;
            }   
        }
        if (!que && !more && j-i+1        if (a[i]>=1 && a[i]<=kind){
            hash[a[i]]–;
            if (hash[a[i]]==min[a[i]]-1) que++;
            if (hash[a[i]]==max[a[i]]) more–;
        }   
    }   
}   

int main(){
    while (scanf("%d%d",&n,&kind)!=EOF){
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        for (int i=1;i<=kind;i++){
            scanf("%d%d",&min[i],&max[i]);
        }   
        memset(hash,0,sizeof(hash));
        work();
        if (ans==0x7FFFFFFF) printf("-1n");
        else printf("%dn",ans);
    }   
}