尺取法：顾名思义就是像尺子一样一段一段去取，保存每次的选取区间的左右端点。然后一直推进
解决问题的思路：
- 先移动右端点 ，右端点推进的时候一般是加
- 然后推进左端点，左端点一般是减
poj 2566
题意：从数列中找出连续序列，使得和的绝对值与目标数之差最小
思路：
- 在原来的数列开头添加一个0
- 每次找到的区间为 [min(i,j)+1,max(i,j)]
应用尺取法的代码：
while (r <=n)
{
int sub = pre[r].sum - pre[l].sum;
while (abs(sub - t) < Min)
{
Min = abs(sub - t);
ansl= min(pre[l].id, pre[r].id) + ;
ansr = max(pre[l].id, pre[r].id);
ans = sub;
}
if (sub < t)
r++;
else if (sub > t) l++;
else break;
if (l == r) r++;
}
解决问题的代码：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + ;
const int INF = 0x7fffffff;
int n, k;
int a[N];
struct node {
int sum, id;
}pre[N];
bool cmp(node a, node b)
{
return a.sum < b.sum;
}
int main()
{
while (scanf("%d%d", &n, &k) != EOF)
{
if (n == && k == ) break;
pre[].id = , pre[].sum = ;
for (int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
pre[i].id = i;
pre[i].sum = pre[i - ].sum + a[i];
}
sort(pre, pre + n + , cmp);
for (int i = ; i < k; i++)
{
int t;
scanf("%d", &t);
int Min = INF;
int l = , r = ;
int ans, ansl, ansr;
while (r <=n)
{
int sub = pre[r].sum - pre[l].sum;
while (abs(sub - t) < Min)
{
Min = abs(sub - t);
ansl= min(pre[l].id, pre[r].id) + ;
ansr = max(pre[l].id, pre[r].id);
ans = sub;
}
if (sub < t)
r++;
else if (sub > t) l++;
else break;
if (l == r) r++;
}
printf("%d %d %d\n", ans, ansl, ansr);
}
}
return ;
}
poj 2739
题意：将一个整数分解为连续的素数之和，有多少种分法?
思路：
- 打表，先打出素数表
- 然后依次查询是否满足条件
用尺取法的代码：
for (;;) {
while (r < size&&sum < n)
{
sum += primes[r++];
}
if (sum < n) break;
else if (sum == n) result++;
sum -= primes[l++];
}解决问题的代码：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define maxn 10000+16
vector<int> primes;
vector<bool> is_prime;
void init_prime()
{
is_prime = vector<bool>(maxn + , true);
is_prime[] = is_prime[] = false;
for (int i = ; i < maxn; i++)
{
if (is_prime[i])
{
primes.push_back(i);
for (int j = i * ; j < maxn; j += i)
{
is_prime[j] = false;
}
}
}
}
int main()
{
int n;
init_prime();
int size = primes.size();
while (cin >> n && n)
{
int result = , sum = ;
int l = ,r = ;
for (;;) {
while (r < size&&sum < n)
{
sum += primes[r++];
}
if (sum < n) break;
else if (sum == n) result++;
sum -= primes[l++];
}
printf("%d\n", result);
}
return ;
}
poj 2100
题意：将一个整数分解为连续数平方之和，有多少种分法？
解决问题的思路：
- 右端点移动，sum+=r*r;
- 如果满足答案就 push (l,r)
- 左端点移动 sum-=l*l;
用尺取法的代码：
for (;;)
{
while (sum < n)
{
sq = r * r;
sum += sq;
r++;
}
if (sq > n) break;
else if (sum == n) ans.push_back(make_pair(l, r));
sum -= l * l;
l++;
}
解决问题的代码：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
using namespace std; typedef long long ll;
vector<pair<ll, ll>> ans;
void solve(ll n)
{
ll l = , r = , sum = , sq;
for (;;)
{
while (sum < n)
{
sq = r * r;
sum += sq;
r++;
}
if (sq > n) break;
else if (sum == n) ans.push_back(make_pair(l, r));
sum -= l * l;
l++;
}
ll size = ans.size();
printf("%lld\n", size);
for (ll i = ; i < size; i++)
{
ll ansr = ans[i].second;
ll ansl = ans[i].first;
printf("%lld",ansr-ansl);
for (ll j=ansl;j<ansr;j++)
printf(" %lld", j);
printf("\n");
}
} int main()
{
ll n;
while (scanf("%lld", &n) != EOF)
{
if (n == ) break;
solve(n);
}
return ;
}