首页 > itarticle > uva 1121 – subsequence

uva 1121 – subsequence

admin 11月 12, 2020 0

Contents

Problem

給一串數字，找出連續最少幾個數字可大於等於 $S$ 。

Solution

記錄目前總和 sum及目前使用第一個的數字 [tail]。只要一加到超過 $S$ ，就持續將 sum 減掉 [tail]，減少數字個數，並一邊記錄個數的最小值。

記得處理無法達到目標的狀況。

Code



int ()
{
    int n, s;
    int num[100000];
    while (scanf("%d%d", &n, &s) != EOF)
    {
        int i;
        for (i = 0; i < n; i++)
            scanf("%d", &num[i]);

        int sum = 0, tail = 0, min = 100000;
        for (i = 0; i < n; i++)
        {
            sum += num[i];
            while (sum >= s)
            {
                min = (i - tail + 1) < min ? (i - tail + 1) : min;
                sum -= num[tail++];
            }
        }

        printf("%dn", min == 100000 ? 0 : min);
    }

    return 0;
}