首页 > 代码库 > POJ - 3320 Jessica's Reading Problem（尺取法+STL）
POJ - 3320 Jessica's Reading Problem（尺取法+STL）
题目链接：http://poj.org/problem?id=3320
题意：一本n页的书（有很多重复的页），要求连续最少页数把这本书每种页都包括进去，求出最少页数。
例如1 8 8 8 1
就1和8两种页，第一次1 8连续两页就把每种页都包括进去了。
尺取法：顾名思义就是一段一段的取。一开始一直往后取，符合条件，然后进行前面减少操作，不符合条件再往后取。
如此重复，得到最优的解。这道题目给出的页的标记好像有特别大的，直接用数组的话会爆炸。
试过用vector,但是对vector的操作太麻烦了。一开始里面没有值，所以对应输出的是一个随机大数。
然后++和--操作还无法成功，要单独拿出来+1。看网上大牛们都是用map，试了下map发现
map里面一开始就把每个对应地点的值初始化为0。再用一个set找到不相同页的数量，整道题就简单了。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <map> 5 #include <set> 6 using namespace std; 7 8 const int N=1000000+10; 9 const int INF=0x3f3f3f3f;10 int a[N];11 12 int main(){13 map <int,int> b;14 set <int> s;15 int n,temp;16 scanf("%d",&n);17 for(int i=0;i<n;i++) {scanf("%d",&a[i]);s.insert(a[i]);}18 int num=s.size();19 int sum=0,ans=INF;20 int st=0,en=0;21 while(1){22 while(sum<num&&en<n){23 if(b[a[en++]]++==0) sum++;24 }25 if(sum<num) break;26 ans=min(ans,en-st);27 if(--b[a[st++]]==0) sum--;28 }29 printf("%d\n",ans);30 return 0;31 }
POJ - 3320 Jessica's Reading Problem（尺取法+STL）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。