给定n个整数表示一个书店《Java入门》连续n天的销售量。如果某天之前销售量在增长,而后一天销售量减少,则称这一天为折点,反过来如果之前销售量减少而后一天销售量增长,也称这一天为折点。其它的天都不是折点。如下图第3天和第6天是折点。 给定n个整数a1, a2, …, an表示每天的销售量,请计算出这些天总共有多少个折点。有一个很奇怪的现象,在这n天中相邻两天的销售量总是不同的,即ai-1≠ai。但是如果两天不相邻,销售量可能相同。 输入共两行。第1行包含一个整数n(3≤n≤365)。第2行包含n个非负整数,表示每天的销售量,两个整数之间用一个空格分隔。 仅一行。一个整数,表示折点出现的数量;若不存在折点,输出0。 样例输入:7 5 4 1 2 3 6 4 样例输出:2
时间: 2024-02-11 17:03:53 浏览: 44
利用JAVA,念整数。
这是一个比较经典的算法问题,可以使用暴力枚举或者一次遍历的方法来解决。下面我给出一种一次遍历的解法,时间复杂度为O(n)。
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int cnt = 0; // 折点的数量
boolean isIncreasing = a[1] > a[0]; // 是否正在上升
for (int i = 2; i < n; i++) {
if (isIncreasing && a[i] < a[i - 1]) { // 上升趋势中出现了下降趋势
cnt++;
isIncreasing = false; // 转换为下降趋势
} else if (!isIncreasing && a[i] > a[i - 1]) { // 下降趋势中出现了上升趋势
cnt++;
isIncreasing = true; // 转换为上升趋势
}
}
System.out.println(cnt);
}
}
```
这个程序读入n个整数表示连续n天的销售量,然后遍历这些销售量。程序使用一个布尔变量`isIncreasing`来表示当前趋势是上升还是下降。如果在上升趋势中出现了下降趋势,或者在下降趋势中出现了上升趋势,那么就说明出现了折点,计数器`cnt`加1,并且将趋势变量`isIncreasing`转换为相反的值。最后,程序输出计数器的值即可。
如果你对这个程序中的某些细节不是很理解,可以让我解释一下。
阅读全文