[C++知识库]CCF CSP 201604-1 折点计数(C语言100分)

1. 问题链接:CCF201604-1 折点计数

给定n个整数a1, a2, …, an表示销售量，请计算出这些天总共有多少个折点。
　　为了减少歧义，我们给定的数据保证：在这n天中相邻两天的销售量总是不同的，即ai-1≠ai。注意，如果两天不相邻，销售量可能相同。输入格式　　输入的第一行包含一个整数n。
　　第二行包含n个整数，用空格分隔，分别表示a1, a2, …, an。输出格式　　输出一个整数，表示折点出现的数量。
样例输入
7
5 4 1 2 3 6 4
样例输出
2
评测用例规模与约定
所有评测用例满足：1 ≤ n ≤ 1000，每天的销售量是不超过10000的非负整数。

2. 问题分析

2.1 两个循环实现

先将所有输入数据存储到数组an中，再遍历数组an统计折点数，容易想到此解法，思维难度较小，但内存空间开销较大

2.2 一个循环实现

先将第1、2个输入数据分别赋值给left、cur变量，再将第3到n个输入数据赋值给right变量，每次循环统计折点数量，然后移动left，cur变量，使得left$\leftarrow$cur,cur$\leftarrow$right，具备一定思考难度，但节省内存空间开销

3. C语言程序实现

3.1 先将输入数据存储到数组再统计折点，即局部极值点数量

#include <stdio.h>
#define N 1000
int an[N+1];

int main()
{
    int n,cnt=0;
    scanf("%d",&n);
    for (int i=0;i<n ;i++ )
    {
        scanf("%d",&an[i]);
    }
    for (int i=1;i<n-1 ;i++ )
    {
        if ((an[i]>an[i-1]&&an[i]>an[i+1])||(an[i]<an[i-1]&&an[i]<an[i+1]))
        {
            cnt++;
        }
    }
    printf("%d\n",cnt);
	return 0;
}

3.2 直接获得输入数据，同时统计折点，即局部极值点数量

#include <stdio.h>

int main()
{
    int n,left,cur,j,right,cnt=0;
    scanf("%d%d%d",&n,&left,&cur);
    for (j=2; j<n ; j++ )
    {
        scanf("%d",&right);
        if ((cur>left&&cur>right)||(cur<left&&cur<right))
        {
            cnt++;
        }
        left=cur;
        cur=right;
    }
    printf("%d\n",cnt);
    return 0;
}