常用技巧精选(一)尺取法
问题描述:给定长度为n的数列非负整数a0,a1,…,an-1以及整数S。求出总和不小于S的连续子序列的长度的最小值。如果解不存在,则输出0。
“林尽水源,便得一山,山有小口,仿佛若有光。便舍船,从口入。初极狭,才通人”
题目分析:对于区间[s,t)上的总和来说如果令
sum(i)=a0+a1+…+ai-1
那么
as +as+1 +… +at-1=sum(t)-sum(s)
因此预先以O(n)的时间计算好sum的话(即前缀和),就可以以O(1)的时间计算区间上的总和。这样一来,子序列的起点s确定以后,便可以用二分搜索快速地确定使序列和不小于S的结尾t的最小值。
“复行数十步,豁然开朗。土地平旷,屋舍俨然,有良田、美池、桑竹之属。”
代码题解:
//输入
int n,S;
int sum[MAX_N];
int sum[MAX_N+1];
void solve(){
//计算sum
for(int i=0;i<n;i++){
sum[i+1]=sum[i]+a[i];
}
if (sum[n]<S){
//解不存在
printf("0\n");
return;
}
int res=n;
for(int s=0;sum[s]+S<=sum[n];s++){
//利用二分搜索求出t
int t=lower_bound(sum+s,sum+n,sum[s]+S)-sum;
res=min(res,t-s);
}
printf("%d\n",res);
}
这个算法的复杂度是O(nlogn),虽然足以一窥桃花源的芳容,但我们还可以更加高效地求解,以深入桃花源一探究竟。
“阡陌交通,鸡犬相闻。其中往来种作,男女衣着,悉如外人。黄发垂髫,并怡然自乐。”
我们设以as开始总和最初大于S时的子序列为as+…+at-1,那么从as+1开始总和最初超过S的连续子序列如果是as+1 +…+ah-1的话,则必然有t<=h。
利用这一性质便可以设计出如下算法:
(1)以s=t=sum=0初始化。
(2)只要依然有sum<S,就不断将sum增加at,并将t增加1。
(3)如果(2)中无法满足sum大于等于S则终止。否则的话,更新res=min(res,t-s)。
(4)将sum减去as,s增加1然后回到(2)。
对于这个算法,因为t最多变化n次,因此只需O(n)的复杂度就可以解决这个问题了。
void solve(){
int res=n+1;
int s=0,t=0,sum=0;
for(;;){
while(t<n&&sum<S){
sum+=a[t++];
}
if(sum<S) break;
res=min(res,t-s);
sum-=a[s++];
}
if(res>n){
//解不存在
res=0;
}
printf("%d/n",res);
}
像这样反复地推进区间地开头和末尾,来求取满足条件的最小区间的方法被称为尺取法
最后欣赏《桃花源记》余下选段,回味悠长~
见渔人,乃大惊,问所从来。具答之。便要还家,设酒杀鸡作食。村中闻有此人,咸来问讯。自云先世避秦时乱,率妻子邑人来此绝境,不复出焉,遂与外人间隔。问今是何世,乃不知有汉,无论魏晋。此人一一为具言所闻,皆叹惋。余人各复延至其家,皆出酒食。停数日,辞去。此中人语云:“不足为外人道也。”
既出,得其船,便扶向路,处处志之。及郡下,诣太守,说如此。太守即遣人随其往,寻向所志,遂迷,不复得路。
南阳刘子骥,高尚士也,闻之,欣然规往。未果,寻病终,后遂无问津者。