• 尺取法
• 应用
  • 寻找区间和
  • 求包含多集合元素的最优解

尺取法

应用背景：
（1）给定一个序列，有时需要它是有序的，先排序
（2）问题和序列的区间有关，且需要操作两个变量，可以用两个下标（指针）i和j扫描区间

应用

寻找区间和

利用双指针寻找区间和
例题：

1. Subsequence
   利用i和j标识滑动窗口的前后位置，因为当前ij段若大于s，则删头；若当前ij段小于s，则应继续加尾。
   例：

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
typedef std::pair<ull,ull> pull;

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;

const int maxm=1e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,s,a[maxm];

void solve(){
	cin>>n>>s;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	bool f=false;
	ll sum=a[1],ans=n+5;
	for(int i=1,j=1;i<=n&&j<=n;){
		if(sum>=s){
			if(ans>j-i+1){//统计答案
				ans=j-i+1;
				f=true;
			}
			sum-=a[i];
			++i;
			if(i>j){
				sum=a[i];
				++j;
			}
		}
		if(sum<s){
			++j;
			sum+=a[j];
		}
	}
	if(f) cout<<ans<<'\n';
	else cout<<0<<'\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

2. Bound Found
   与上面的题不同，这里需要利用前缀和转换一下，利用前缀和将滑动窗口显现出来，再利用尺取法找与题给的数字t差的绝对值最小的连续子序列
   摘记：古怪的编译器。。。还得了解了解poj的c++和g++的区别

//>>>Qiansui
//g++过的
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long
// typedef pair<int,int> pii;
// typedef pair<ll,ll> pll;
// typedef pair<ull,ull> pull;

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
const int maxm=1e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,k,a[maxm],t;
pair<ll,int> sum[maxm];

void solve(){
	while(1){
		cin>>n>>k;
		if(n==0) break;
		sum[0]=make_pair(0,0);
		for(int i=1;i<=n;++i){
			cin>>a[i];
			sum[i]=make_pair(sum[i-1].first+a[i],i);
		}
		sort(sum,sum+1+n);//注意从0开始,因为前缀和
		for(int z=0;z<k;++z){
			cin>>t;
			ll ans,l,r,cha=inf,ss;
			for(int i=0,j=1;j<=n&&i<=n;){
				ss=sum[j].first-sum[i].first;
				if(llabs(ss-t)<=cha){//找到一个更小的
					ans=ss;
					cha=llabs(ss-t);
					l=sum[i].second;
					r=sum[j].second;
				}
				if(ss>t) ++i;
				else if(ss<t) ++j;
				else break;
				if(i==j) ++j;
			}
			if(r<l) swap(l,r);//保证顺序，左在l，右在r
			cout<<ans<<' '<<l+1<<' '<<r<<'\n';//左区间需要加一
		}
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

求包含多集合元素的最优解

2023杭电多校第四场 - 3 Simple Set Problem