【尺取法】

尺取法

POJ3061 Subsequence

给定一个序列，使得其和大于或等于S，求最短的子序列长度。

如果一个区间其和(ge S)了，那么不需要再向后推右端点了，因为其和也肯定(ge S)但长度更长，所以，当区间和(< S)时右端点向右移，和(ge S)时，左端点向右移以进一步找到最短的区间，如果右端点移动到区间末尾其和还不大于等于S，结束区间的枚举

int main(){
	int T;rd(T);
	while(T--){
		rd(n),rd(s);
		for(int i=1;i<=n;++i) rd(a[i]);
		int l=1,r=0;ans=inf,sum=0;
		while(1){
			while(r<n&&sum<s) sum+=a[++r];
			if(sum<s) break;
			ans=Min(ans,r-l+1),sum-=a[l++];
		}
		if(ans==inf) puts("0");
		else printf("%d
",ans);
	}
	return 0;
}

POJ3320 Jessica's Reading Problem

一本书有P页，每一页都一个知识点，求去最少的连续页数覆盖所有的知识点。

如果一个区间的子区间满足条件，那么在区间推进到该处时，右端点会固定，左端点会向右移动到其子区间，且其子区间会是更短的，只是需要存储所选取的区间的知识点的数量，那么使用map进行映射以快速判断是否所选取的页数是否覆盖了所有的知识点

int n,m,a[N];
map<int,int>h;
set<int> s;
int main(){
	rd(n);
	for(int i=1;i<=n;++i) rd(a[i]),s.insert(a[i]);
	m=s.size();
	int l=1,r=0,ans=inf,nw=0;
	while(1){
		while(r<n&&nw<m) if(!h[a[++r]]++) ++nw;
		if(nw<m) break;
		ans=Min(ans,r-l+1);
		if(--h[a[l++]]==0) --nw;
	}
	printf("%d",ans);
	return 0;
}

luogu1638逛画展和它差不多

int n,m,a[N],cnt[M];
int main(){
	rd(n),rd(m);
	for(int i=1;i<=n;++i) rd(a[i]);
	int l=1,r=0,nw=0,ans=inf,ansl,ansr;
	while(1){
		while(r<n&&nw<m) if(!cnt[a[++r]]++) ++nw;
		if(nw<m) break;
		if(ans>r-l+1) ans=r-l+1,ansl=l,ansr=r;
		if(!--cnt[a[l++]]) --nw;
	}
	printf("%d %d",ansl,ansr);
	return 0;
}

POJ2566 Bound Found

给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小，如果存在多个，任意解都可行。

要找到一个子区间使得和最接近t的话，那么不断地找比当前区间的和更大的区间，如果区间和已经大于等于t了，那么不需要在去找更大的区间了，因为其和与t的差值更大，然后区间左端点向右移动推进即可。所以，首先根据计算出所有的区间和，

排序之后按照上面的思路求解即可。

int n,k,a[N];
pii sum[N];
int main(){
	while(scanf("%d%d",&n,&k)!=EOF&&n+k){
		sum[0]=pii(0,0);
		for(int i=1;i<=n;++i) rd(a[i]),sum[i]=pii(sum[i-1].first+a[i],i);
		sort(sum,sum+n+1);
		for(int i=1;i<=k;++i){
			int tmp=inf,st=0,ed=1,l,r;
			ll ans,nw,x;
			rd(x);
			while(ed<=n){
				nw=sum[ed].first-sum[st].first;
				if(Abs(x-nw)<tmp) tmp=Abs(x-nw),ans=nw,l=sum[st].second,r=sum[ed].second;
				if(nw>x) ++st;
				else if(nw<x) ++ed;
				else break;
				if(st==ed) ++ed;
			}
			if(r<l) swap(r,l);
			printf("%lld %d %d
",ans,l+1,r);
		}
	}
	return 0;
}

SCOI2008生日礼物

==其实就是逛画展

int n,m,cnt[100];
struct node{int kind,po;}a[N];
bool cmp(node A,node B){return A.po<B.po;}
int main(){
	rd(n),rd(m);
	for(int j=1,i=0,x;j<=m;++j){
		rd(x);
		while(x--) a[++i].kind=j,rd(a[i].po);
	}
	sort(a+1,a+n+1,cmp);
	int l=1,r=0,nw=0,ans=inf;
	while(1){
		while(r<n&&nw<m){
			if(!cnt[a[++r].kind]++) ++nw;
			while(a[r+1].po==a[r].po) if(!cnt[a[++r].kind]++) ++nw;
		}
		if(nw<m) break;
		ans=Min(ans,a[r].po-a[l].po);
		if(!--cnt[a[l++].kind]) --nw;
		while(a[l+1].po==a[l].po) if(!--cnt[a[l++].kind]) --nw;
	}
	printf("%d",ans);
	return 0;
}