尺取法通常指的是保存数组的一组下标(起点和终点),然后根据实际情况,交替地推进这两个下标,然后获得结果的方法。
其实就很像毛毛虫在前进的时候蠕动身体的过程。
题目:http://poj.org/problem?id=3061
方法1:先对数组求前缀和sum。然后对于sum数组,从第0位开始一直往右,利用upper_bound,计算出第一个大于sum[i]+S的坐标,然后计算区间长度t-s,利用min(ans, t-s)来更新ans。本方法时间复杂度为O(NlogN)。
方法2:利用“若s~t的a[i]的和刚好满足sum>S,则对于s+1~t’,也刚好满足sum>S的话,需要t’≥t,这一性质。就可以在O(N)的时间内完成求解。
方法1的AC代码:
#include <iostream>
#include <string.h>
#include<algorithm>
using namespace std;
#define MAXN 100005
typedef long long ll;
ll pre[MAXN];
int main()
{
int t, n;
ll s;
int tmp;
scanf("%d", &t);
while (t--)
{
memset(pre, 0, sizeof(pre));
scanf("%d%lld", &n, &s);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &tmp);
pre[i] = pre[i - 1] + tmp;
}
//无解
if(pre[n]<s)
{
printf("0\n");
continue;
}
//尺取法
int min_len = MAXN;
for(int st = 0;pre[st]+s<=pre[n];++st)
{
min_len = min(min_len, int(lower_bound(pre+st, pre+n, pre[st]+s)-pre-st));
}
printf("%d\n", min_len);
}
}
方法2的AC代码:
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
int a[MAXN];
int t, n;
ll s;
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%lld", &n, &s);
memset(a, 0, sizeof(a));
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
}
int st = 0, to = 0;
ll sum = 0;
int ans = (1 << 30);
while (1)
{
while (sum < s && to < n)
{
sum += a[to];
++to;
}
if (sum < s)
break;
ans = min(ans, to - st);
sum -= a[st];
++st;
}
if (ans > n)
{
ans = 0;
}
printf("%d\n", ans);
}
}
题目:http://poj.org/problem?id=3320
这题的思路和上题的方法2相似,在某个区间[s,t]已经覆盖了所有知识点的情况下,这时去除区间头,然后继续寻找下一个结果。
AC代码:
#include <map>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
#define MAXN 1000006
int a[MAXN];
int p;
int main()
{
scanf("%d", &p);
set<int> tmp_set;
for (int i = 0; i < p; ++i)
{
scanf("%d", &a[i]);
tmp_set.insert(a[i]);
}
int st = 0, to = 0;
map<int, int> mp;
int ans = MAXN;
int kinds = tmp_set.size();
int current_kinds = 0;
while (1)
{
while (to < p && current_kinds < kinds)
{
if (mp[a[to]] == 0)
{
//出现新的知识点
mp[a[to]] = 1;
++current_kinds;
}
else
++mp[a[to]];
++to;
}
if (current_kinds < kinds)
break;
ans = min(ans, to - st);
mp[a[st]]--;
if (mp[a[st]] == 0)
--current_kinds;
++st;
}
printf("%d\n", ans);
}