正常血压

题意

若收缩压和舒张压都在给定闭区间内则正常，求连续正常血压的最长小时数。

思路

维护 current 表示以当前时刻结尾的连续正常长度，longest 记录历史最大值。正常时递增并更新最大值，异常时将 current 清零。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12measurement_count = int(input())
current = longest = 0

for _ in range(measurement_count):
    systolic, diastolic = map(int, input().split())
    if 90 <= systolic <= 140 and 60 <= diastolic <= 90:
        current += 1
        longest = max(longest, current)
    else:
        current = 0

print(longest)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#include <cstdio>
int main(){
    int n,a,b,c = 0,max = -1;
    scanf("%d",&n);
    int i;
    for (i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        if( a  < 90 || a > 140 || b <60 || b > 90){
            if( max < c )
                max = c;
            c = 0;
        }
        else {
            c++;
        }
    }
    if( max < c )
        max = c;
    printf("%d\n",max);
    return 0;
}

复杂度

时间复杂度为 $O(n)$ ，额外空间复杂度为 $O(1)$ 。

总结

最长连续段的通用状态是“当前段长度”和“历史最大长度”。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结