文章目錄

• 題目大意
• 解題思路
• 代碼
• 注意

題目大意

解題思路

(1): 二分思想: 對區間長度進行二分搜索，對某一長度l：

• 初始化$0$到$l?1$號各個知識點數量，并記錄知識點種類數。
• 線性掃描，過程中更新知識點數量，并依據條件更新知識點種類。
• 若過程中種類數達到總知識點數，則該長度可解。

復雜度大概$O(n(logn{)}^2)$, 超時。

(2): 尺寸法: 復雜度$O(nlogn)$, 通過

代碼

• 二分法，必須吧r設置為P。

#include<iostream> #include<set> #include<map> #include<stdio.h> #include<cstring> using namespace std; const int MAXP = 1000000+5; int P; int books[MAXP]; int Z; set<int> idea; map<int, int>idea2num; int main() {while(scanf("%d", &P)!=EOF){idea.clear();idea2num.clear();for(int i=0; i<P; i++){scanf("%d", &books[i]);idea.insert(books[i]);}Z = idea.size();int l = 1; int r = P;int ans = P;while(l < r){int mid = (l+r)/2;int now_idea = 0;set<int>::iterator ite;for(ite = idea.begin(); ite!=idea.end(); ite++)idea2num[*ite] = 0;for(int i=0; i<mid; i++)if(idea2num[books[i]]++ == 0)now_idea++;for(int i=0; i+mid<P; i++){if(now_idea == Z)break;if(--idea2num[books[i]] == 0)now_idea--;if(idea2num[books[i+mid]]++ == 0)now_idea++;}if(now_idea == Z){ans = min(ans, mid);r = mid;}elsel = mid + 1;}printf("%d\n", ans);}return 0; }

注意

• 尺寸法。

#include<iostream> #include<set> #include<map> #include<stdio.h> using namespace std;const int MAXP = 1000000+5; set<int> idea; map<int, int> idea2count; int books[MAXP]; int main() {int N;while(scanf("%d", &N)!=EOF){idea.clear();idea2count.clear();for(int i=0; i<N; i++){scanf("%d", &books[i]);idea.insert(books[i]);idea2count[books[i]] = 0;}int Z = idea.size();int sum = 0;int s = 0; int e = -1;int ans = N;while(!(e == N-1 && sum < Z)){if(e < N - 1 && sum < Z){e++;if(idea2count[books[e]]++ == 0){sum++;}}if(s < N-1 && sum == Z){ans = min(ans, e-s+1);if(--idea2count[books[s++]] == 0)sum--;}}printf("%d\n", ans);}return 0; }

總結

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

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