poj3061 poj3320 poj2566尺取法基础（一）

poj3061 给定一个序列找出最短的子序列长度，使得其和大于等于S

那么只要用两个下标，区间和小于S时右端点向右移动，区间和大于S时左端点向右移动，在这个过程中更新Min

#include <cstdio>

#include <algorithm>

#include <cstring>

#define MAX 100005

#define LL long long

#define INF 0x3f3f3f3f

using namespace std;

LL a[];

int n, t, ans = INF;

LL sum, s;

int main()

{

    scanf("%d", &t);

    while (t--){

        scanf("%d %I64d", &n, &s);

        for (int i = ; i < n; i++) scanf("%I64d", a+i);

        int st = , en = ;

        ans = INF; sum = ;

        while (){

            while (en<n && sum<s) sum += a[en++];

            if (sum < s) break;

            ans = min(ans, en-st);

            sum -= a[st++];

        }

        if (ans == INF) ans = ;

        printf("%d\n", ans);

    }

    return ;

}

poj3320给一本书有P页，每页都有一个知识点，求最少的连续页数覆盖所有知识点

如果一个区间的子区间满足条件，那么右端点固定，左端点推进

反之左端点固定 ，右端点推进么。需要用map进行映射，set求总共有多少知识点

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <set>

#include <map>

#define MAX 1000010

#define LL long long

#define INF 0x3f3f3f3f

using namespace std;

int a[MAX];

map <int, int> cnt;

set <int> t;

int p, ans = INF, st, en, sum;

int main()

{

    scanf("%d", &p);

    for (int i = ; i < p; i++) scanf("%d", a+i), t.insert(a[i]);

    int num = t.size();

    while (){

        while (en<p && sum<num)

            if (cnt[a[en++]]++ == ) sum++;

        if (sum < num) break;

        ans = min(ans, en-st);

        if (--cnt[a[st++]] == ) sum--;

    }

    printf("%d\n", ans);

    return ;

}

poj2566 给定一个数组和值t，求一个子区间使得其和的绝对值与t的差值最小

有正有负，不能保证单调性，无法单点拓展边界，预处理出所有的前缀和，升序排列

然后尺取法求出两个端点，使区间和的绝对值最逼近t

#include <cstdio>

#include <algorithm>

#include <cstring>

#define INF 0x3f3f3f3f

#define LL long long

#define MAX 100010

using namespace std;

typedef pair<LL, int> p;

LL a[MAX], t, ans, tmp, b;

int n, k, l, u, st, en;

p sum[MAX];

LL myabs(LL x)

{

    return x>=? x:-x;

}

int main()

{

    while (scanf("%d %d", &n, &k), n+k){

        sum[] = p(, );

        for (int i = ; i <= n; i++){

            scanf("%I64d", a+i);

            sum[i] = p(sum[i-].first+a[i], i);

        }

        sort(sum, sum++n);

        while (k--){

            scanf("%I64d", &t);

            tmp = INF; st = , en = ;

            while(en <= n){

                b = sum[en].first-sum[st].first;

                if(myabs(t-b) < tmp){

                    tmp = myabs(t-b);

                    ans = b;

                    l = sum[st].second; u = sum[en].second;

                }

                if(b > t) st++;

                else if(b < t) en++;

                else break;

                if(st == en) en++;

            }

            if (u < l) swap(u, l);

            printf("%I64d %d %d\n", ans, l+, u);

        }

    }

    return ;

}