算法--尺取法
尺取法
尺取法通常是指对数组保存一对下标（起点，终点），然后根据实际情况交替推进两个端点直到得出答案的方法，这种操作很像是尺取虫爬行的方式故得名。
我们先来看看POJ的第3061题：
Subsequence
| Time Limit: 1000MS | Memory Limit: 65536K |
| Total Submissions: 10657 | Accepted: 4418 |
Description
A sequence of Npositive integers (10 < N < 100 000), each of them less than or equal10000, and a positive integer S (S < 100 000 000) are given. Write a programto find the minimal length of the subsequence of consecutive elements of thesequence, the sum of which is greater than or equal to S.
Input
The first line isthe number of test cases. For each test case the program has to read thenumbers N and S, separated by an interval, from the first line. The numbers ofthe sequence are given in the second line of the test case, separated byintervals. The input will finish with the end of file.
Output
For each the casethe program has to print the result on separate line of the output file.if noanswer, print 0.
Sample Input
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
Sample Output
2
3
题目基本上只这样的，给定长度为n的数列整数a0,a1…..an-1以及整数S。求出总和不小于S的连续子序列的长度的最小值。如果不存在输出0。
比如第一组数据5+10长度为二，第二组数据3+4+5长度为三。
void solve()
{
inti;
for(i=0;i<n;i++)
{
sum[i+1]=sum[i]+a[i];
}
if(sum[n]<S)
{
printf(“0\n”);
return;
}
intres=n;
for(ints=0;sum[s]+S<=sum[n];s++)
{
//利用二分搜索求出t
intt=lower_bound(sum+s,sum+n,sum[s]+S)-sum;
//t表示了第一个大于或等于sum[s]+S的数的下标
res=min(res,t-s);
}
printf(“%d\n”,res);
}
我们看到这种方法可以满足我们的要求，但是尺取法会更加高效。
void solve()
{
intres=n+1;
ints=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);
}
像这样反复地推进区间的开头和结尾，来求取满足条件的最小区间的方法被称为尺取法。
推荐题目POJ 3320
第六届福建省大学生程序设计竞赛 Problem E The Longest Straight
矫情吗；*
深藏阁楼爱情的钟
￡神魔★判官ぃ
红太狼
小灰灰
柔情只为你懂
还没有评论，来说两句吧...