尺取法

尺取，取的是：多段等效区间（等效体现在：满足题目要求）

某些时候需要保证数列的单调性才能使用

POJ 3061

Description

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file.if no answer, 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的数列，求出总和不小于S的连续子序列的最小长度

思路

“连续子序列”体现尺取的特点，而且不需要数列单调

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int t, n, s;
int a[100005];

void slove()
{
    int ans = n;
    int l = 0, r = 0, sum = 0, len = 0;
    while(r <= n - 1)
    {
        while(sum < s && r <= n - 1)
        {
            sum += a[r];
            ++r;
            ++len;
        }
        while(sum >= s)///退出时sum < s(所以下面len + 1)
        {
            sum -= a[l];
            ++l;
            --len;
        }
        ans = min(ans, len + 1);
    }
    cout << ans << '\n';
}

int main()
{
    cin >> t;
    while(t--)
    {
        int sum = 0;
        scanf("%d%d", &n, &s);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        if(sum < s)
            cout << '0' << '\n';
        else
            slove();
    }
    return 0;
}

POJ 2566

题目大意

给出一个整数列，求一段子序列之和的绝对值最接近所给出的t。输出该段子序列之和及左右端点。

思路

PS：（任意两个前缀和的差值取abs）得到对应区间的和的abs

此题等效区间的“等效”在于：某个区间和的abs（即某两个前缀和的差值）十分接近t

1.输入时计算前缀和（sum[i].val）及当前位置(sum[i].pos)

2.根据val排序

3.依次尺取得到一个个的某区间的和的abs，这些值是某种意义上的“等效”

（正是由于排序才有的一段段等效区间）

4.更新（不断更新至遍历完成找到答案）

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
const int inf = 0x3f3f3f3f;

int n, k;
struct LX
{
    int val, pos;
}sum[N];

bool cmp(LX a, LX b)
{
    return a.val < b.val;
}

void slove(int t)
{
    int tem;///某个区间和的绝对值
    int mmin = inf;///tem与t的最小差值
    int ans;
    int l = 0, r = 1, tl = l, tr = r;///L从0开始不会漏区间
    while(r <= n && mmin != 0)
    {
        ///不要以为sum[2] - sum[4]是不合理的（是区间[3,4]内元素和的abs）
        ///这里tem取的是区间[l + 1, r]
        tem = abs(sum[r].val - sum[l].val);
        if(abs(tem - t) < mmin)///更新
        {
            mmin = abs(tem - t);
            ans = tem;
            tl = sum[l].pos;
            tr = sum[r].pos;
        }
        if(tem < t)
            r++;
        if(tem > t)
            l++;
        if(l == r)
            r++;
    }
    if(tl > tr)
        swap(tl, tr);
    cout << ans << ' ' << tl + 1 << ' ' << tr << '\n';
}

int main()
{
//    freopen("00in.txt", "r", stdin);
    while(~scanf("%d%d", &n, &k) && n && k)
    {
        int t;
        int tem = 0;
        sum[0].val = 0;
        sum[0].pos = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &tem);
            sum[i].val = sum[i - 1].val + tem;
            sum[i].pos = i;
        }
        sort(sum , sum + 1 + n, cmp);///0也参与排序可检测区间[1,1]
//        for(int i = 0; i <= n; ++i)
//            cout << sum[i].val << ' ';
//        cout << '\n';
        for(int i = 0; i < k; ++i)
        {
            scanf("%d", &t);
            slove(t);
        }
    }
    return 0;
}