解題區/解題區 - UVa

UVa 13070 - Palm trees in the snow

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一排棕梠樹的樹高 $H_i$，經過大雪後，高度 $H_i \ge W$ 的樹都會攤倒，挑選一個區間滿足最多五棵屹立不搖的情況下，請問區間長度最長為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
3
30
10
10  30  50  20  40  60  30  40  50  36
40
10
10  30  50  20  40  20  10  10  20  36
20
3
40  10  15

Sample Output

1
2
3
7
10
3

Solution

將會倒的位置記錄下來，線性掃描過去即可。

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int W, N, x;
        scanf("%d %d", &W, &N);
        vector<int> A;
        A.push_back(-1);
        for (int i = 0; i < N; i++) {
            scanf("%d", &x);
            if (x >= W)
                A.push_back(i);
        }
        A.push_back(N);
        int ret = 0;
        for (int i = 1; i < A.size()-1; i++) {
            int x = A[min(i+5, (int)A.size()-1)];
            ret = max(ret, x - A[i-1]-1);
        }
        if (A.size() == 2)	ret = N;
        printf("%d\n", ret);
    }
    return 0;
}