PAT Basic 1112. 超标区间

1. 题目描述：

上图是用某科学研究中采集的数据绘制成的折线图，其中红色横线表示正常数据的阈值（在此图中阈值是 25）。你的任务就是把超出阈值的非正常数据所在的区间找出来。例如上图中横轴 [3, 5] 区间中的 3 个数据点超标，横轴上点 9 （可以表示为区间 [9, 9]）对应的数据点也超标。

2. 输入格式：

输入第一行给出两个正整数 \(N\)（\(≤10^4\)）和 \(T\)（\(≤100\)），分别是数据点的数量和阈值。第二行给出 \(N\) 个数据点的纵坐标，均为不超过 1000 的正整数，对应的横坐标为整数 0 到 \(N−1\)。

3. 输出格式：

按从左到右的顺序输出超标数据的区间，每个区间占一行，格式为 [A, B]，其中 A 和 B 为区间的左右端点。如果没有数据超标，则在一行中输出所有数据的最大值。

4. 输入样例：

11 25
21 15 25 28 35 27 20 24 18 32 23

11 40
21 15 25 28 35 27 20 24 18 32 23

5. 输出样例：

[3, 5]
[9, 9]

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

维护变量outputFlag标记当前是否在超出阈值的区间内，进入区间时输出左端点，离开区间时输出右端点即可。维护变量maxData记录最大数据值，变量firstBlood记录是否存在超出阈值的区间。第一次提交时testpoint2，3，4报wrong answer，检查代码后发现逻辑判断存在bug，若在最后一个数据点进入超出阈值的区间，不会输出右端点（即这个数据点本身），加上尾处理后AC。

My Code:

#include <stdio.h>

// first submit testpoint 2, 3, 4 wrong answer
int main(void)
{
    int dataCount=0, threshold=0;
    int maxData=0, tempData=0;
    int outputFlag = 0;
    int i=0; // iterator
    int firstBlood=0; // flag of have reach threshold
    
    scanf("%d%d", &dataCount, &threshold);
    
    maxData = -1;
    for(i=0; i<dataCount; ++i)
    {
        scanf("%d", &tempData);
        if(maxData < tempData) maxData = tempData;
        
        if(!outputFlag && tempData>threshold) // output Left endpoint of interval
        {
            firstBlood = 1;
            outputFlag = 1;
            printf("[%d, ", i);
        }
        else if(outputFlag && tempData<=threshold)
        {
            outputFlag = 0;
            printf("%d]\n", i-1);
        }
        
    }
    
    if(outputFlag) // tail handle, this fixed testpoint2, 3, 4
    {
        outputFlag = 0;
        printf("%d]\n", i-1);
    }
    
    if(!firstBlood) printf("%d\n", maxData);
    
    return 0;
}