Description

Star 計(jì)劃訂購一本將要發(fā)行的周刊雜志，但他可不是為了讀書，而是—— 集卡。 已知雜志將要發(fā)行 N 周（也就是 N 期），每期都會(huì)附贈(zèng)一張卡片。Star 通 過種種途徑，了解到 N 期雜志附贈(zèng)的卡片種類。Star 只想訂購連續(xù)的若干期， 并在這些期內(nèi)收集所有可能出現(xiàn)的種類的卡片。現(xiàn)在他想知道，他最少需要訂 購多少期。

Input

第一行一個(gè)整數(shù) N；
第二行一個(gè)長度為 N 的字符串，由大寫或小寫字母組成，第 i 個(gè)字符表示 第 i 期附贈(zèng)的卡片種類，每種字符（區(qū)分大小寫）表示一種卡片。

Output

輸出一行一個(gè)整數(shù)，表示 Star 最少訂購的期數(shù)。

Sample Input

8
acbbbcca

Sample Output

3

Data Constraint

對(duì)于 30%的數(shù)據(jù)，N ≤ 300；
對(duì)于 40%的數(shù)據(jù)，N ≤ 2000；
對(duì)于 60%的數(shù)據(jù)，N ≤ 5000；
對(duì)于 80%的數(shù)據(jù)，N ≤ 100000；
對(duì)于 100%的數(shù)據(jù)，N ≤ 500000。

Solution

• 這題的題意就是給你一段包含多種元素序列，求最短的一段連續(xù)的區(qū)間包含所有種類的元素。

• 那么就有各種解決的方法了，我的方法是 O(NlogN) 的。（聽說 O(N) 掃一遍就可以了）

• 先二分答案 Mid ，把原問題轉(zhuǎn)化成判定性問題。

• 在將長為 Mid 的區(qū)間一格一格地從左向右移動(dòng)，一邊加進(jìn)一個(gè)新元素，一邊刪去。

• 中途用一個(gè)標(biāo)志數(shù)組 Bz[i] 表示 i 這個(gè)字母在區(qū)間中出現(xiàn)的多少次，

• 并維護(hù)包含的元素種類是否達(dá)到全部即可，這樣的復(fù)雜度是 O(N) 。

• 再結(jié)合上二分，總時(shí)間復(fù)雜度就是 O(NlogN) ，秒過本題。

Code

#include<cstdio> #include<cstring> using namespace std; int n,num; int a[500001],bz[150]; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){char ch=getchar();while(!('A'<=ch && ch<='Z' || 'a'<=ch && ch<='z')) ch=getchar();if(++bz[a[i]=ch]==1) num++;}int l=1,r=n;while(l<r){int mid=(l+r)>>1,k=0;memset(bz,0,sizeof(bz));for(int i=1;i<=mid && k<num;i++)if(++bz[a[i]]==1) k++;if(k==num){r=mid;continue;}for(int i=mid+1;i<=n && k<num;i++){if(++bz[a[i]]==1) k++;if(!--bz[a[i-mid]]) k--;}if(k==num) r=mid; else l=mid+1;}printf("%d",l);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 100046. 【NOIP2017提高A组模拟7.14】收集卡片的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。