2018-2-7

與poj3061類似，直接使用尺取法即可，這里使用STL里面的map求解更為方便，可以直接得到每個知識點出現的次數，繼而便于進行加一減一操作。

#include<iostream> #include<cstdio> #include<map> using namespace std;const int N = 1000000; int x[N+1]; int p,cnt; map<int,int>mp;void res(){int i=1,j=1,res=N;for (i=1;i<=p;i++){while (mp.size()!=cnt&&j<=p){if (mp.count(x[j])){mp[x[j]]++;}else{mp[x[j]]=1;}j++;}if (mp.size()!=cnt) break;res=min(res,j-i);if (mp[x[i]]==1){mp.erase(x[i]);}else{mp[x[i]]--;}}cout<<res<<endl; }int main(){while (cin>>p){mp.clear();for (int i=1;i<=p;i++){scanf ("%d",&x[i]);if (mp.count(x[i])){mp[x[i]]++;}else{mp[x[i]]=1;}}cnt=mp.size();mp.clear();res();}return 0; }

總結

以上是生活随笔為你收集整理的poj3320 尺取法 挑战程序设计竞赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。