Problem Solving►UVa

UVa 1121 - Subsequence

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

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

Solution

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

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

Code

UVa 1121
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>

int main()
{
    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("%d\n", min == 100000 ? 0 : min);
    }

    return 0;
}