POJ 3061 Subsequence

Description

n个非负整数，给出S，求一个连续子序列，其和>= S，并使其长度最小

http://poj.org/problem?id=3061

Idea(二分搜索)

连续子序列、和 -> 暗示前缀和

因为没有负数，前缀和sum[]是单调递增的

单调递增这一特点对应 ①尺取法、②lower_bound查找

Code(二分搜索)

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

int a[100005];
int sum[100005];///涉及 连续子序列的和 -> 前缀和
///因为没有负数，前缀和sum[]是单调递增的
///单调递增这一特点对应 ①尺取法、②lower_bound查找

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, tot;
        cin >> n >> tot;
        cin >> a[0];
        sum[0] = a[0];
        for(int i = 1; i < n; ++i)
        {
            scanf("%d", &a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
        if(sum[n - 1] < tot)
        {
            cout << '0' << '\n';
            continue;
        }
        int ans = n;
        for(int i = 0; sum[n - 1] - sum[i] >= tot; ++i)
        {    /// (sum + i) 为起点 (sum + pos) 为终点
            int pos = lower_bound(sum + i, sum + n, sum[i] + tot) - sum;
            ans = min(ans, pos - i);
        }
        cout << ans << '\n';
    }
return 0;
}

Code(尺取法)

#include <cstdio>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;

int a[100005];

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, tot;
        cin >> n >> tot;
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        int res = INF, l = 0, r = 0, sum = 0;
        while(1)
        {
            while(r < n && sum < tot)
                sum += a[r++];
            if(sum < tot)
                break;
            else
            {
                res = min(res, r - l);
                sum -= a[l];
                l++;
            }
        }
        if(res == INF)
            cout << '0' << '\n';
        else
            cout << res << '\n';
    }
    return 0;
}