题解：UVA11496 Musical Loop

UVA11496 Musical Loop

题目大意

给定一段循环音乐每个音符的音高，询问有多少个音符位于“峰”（相邻音符音高均低于它）或“谷”（相邻音符音高均高于它）。数据保证没有两个相邻音符的音高相同。

解题思路

直接模拟即可。

记录每个音符的音高分别为 $a_1, a_2, \dots, a_n$。为了模拟出“循环”的效果，赋值 $a_0 = a_n, a_{n+1} = a_1$。对于 $a_1, a_2, \dots, a_n$ 中的每个值 $a_i$，如果 $a_i - a_{i-1}$ 与 $a_i - a_{i+1}$ 同号，则 $a_i$ 位于“峰”或“谷”处。同号可以用乘积大于 $0$ 来判断。

代码

#include <iostream>
using namespace std;

inline int read() {
    char c = getchar();
    int  x = 0, f = 1;
    for (; !isdigit(c); c = getchar())
        if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x * f;
}

#define r(a) (a) = read()

int N;
int H[10005];

signed main() {
    while (1) {
        r(N);
        if (!N) break;
        for (int i = 1; i <= N; i++) r(H[i]);
        H[N + 1] = H[1];
        H[0]     = H[N];
        int ans  = 0;
        for (int i = 1; i <= N; i++)
            if ((H[i] - H[i - 1]) * (H[i] - H[i + 1]) > 0) ans++;
        printf("%d\n", ans);
    }
    return 0;
}