首页 > 代码库 > poj3061 Subsequence&&poj3320 Jessica's Reading Problem(尺取法)
poj3061 Subsequence&&poj3320 Jessica's Reading Problem(尺取法)
这两道题都是用的尺取法。尺取法是《挑战程序设计竞赛》里讲的一种常用技巧。
就是O（n）的扫一遍数组，扫完了答案也就出来了，这过程中要求问题具有这样的性质：头指针向前走（s++）以后，尾指针（t）要么不动要么也往前走。满足这种特点的就可以考虑尺取法。
poj3061 比较简单，也可以用二分做，时间复杂度O（n*logn）。用尺取法可以O（n）解决。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long intint T,N,S,a[100010];int main(){ //freopen("in7.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&T); while(T--) { scanf("%d%d",&N,&S); int ans=INF; for(int i=0;i<N;i++) { scanf("%d",&a[i]); } int s=0,t=0,sum=0; while(1) { while(t<N&&sum<S) { sum+=a[t]; t++; } if(sum<S) break; ans=min(ans,t-s); //注意这里的距离不是(t-s+1),因为我前一个while中最后t++了，所以 //现在是s到t的左闭右开区间 sum-=a[s]; s++; } if(ans<INF) cout<<ans<<endl; else cout<<‘0‘<<endl; } //fclose(stdin); //fclose(stdout); return 0;}
poj3320 对数据用set和map来处理显得很方便，核心部分也是尺取法。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long intint P,a[1000010];set<int>st;map<int,int>mp;int main(){ // freopen("in8.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&P); for(int i=0;i<P;i++) { scanf("%d",&a[i]); st.insert(a[i]); } int tol=st.size(); int s=0,t=0; int ans=INF; for(;;) { while(t<P&&mp.size()<tol) { if(mp.count(a[t])) mp[a[t++]]++; /*在map里用count函数，有返回1，没有就返回0*/ else mp[a[t++]]=1; } if(mp.size()<tol) break; ans=min(ans,t-s); mp[a[s]]--; if(mp[a[s]]==0) mp.erase(a[s]); s++; } cout<<ans<<endl; //fclose(stdin); //fclose(stdout); return 0;}
poj3061 Subsequence&&poj3320 Jessica's Reading Problem(尺取法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。