首页 > 分享 > 摆花的人 (flower)

摆花的人 (flower)

花匠小妙招
2025-02-19 18:04

摆花的人 (flower)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

在曾经的讲解中，花和他的兄弟姐妹们被这个叫做 Y y x Yyx Yyx 的人摆来摆去，吓得耳朵都瞎了，嘴巴也听不见了。于是他们决定「以其人之道还治其人之身」，他们把 Y y x , K a n g k a n g , M i c h a e l Yyx, Kangkang, Michael Yyx,Kangkang,Michael 等人摆成一排，这个时候，花说道：「你们的身高太不和谐了，只有满足我的要求的人才能留下，其他人都去当花。」而 Y y x Yyx Yyx 想留下尽量多的同胞们，于是他来找你了。
具体而言，人的高度可以看成一列整数 h 1 , h 2 , . . . , h n h_1,h_2,...,h_n h1,h2,...,hn。
设当一部分人出去后，剩下的人的高度依次为 g 1 , g 2 , . . . , g m g_1,g_2,...,g_m g1,g2,...,gm ，则花们希望下面两个条件中至少有一个满足：
·条件A ：对于所有 g 2 i > g 2 i − 1 , g 2 i > g 2 i + 1 g_{2i}>g_{2i-1},g_{2i}>g_{2i+1} g2i>g2i−1,g2i>g2i+1。
·条件B ：对于所有 g 2 i < g 2 i − 1 , g 2 i < g 2 i + 1 g_{2i}<g_{2i-1},g_{2i}<g_{2i+1} g2i<g2i−1,g2i<g2i+1。。
注意上面两个条件在 n = 1 n=1 n=1 时同时满足，当 n > 1 n > 1 n>1时最多有一个能满足。

输入

第一行包含一个正整数 n n n ，表示开始时的人数。
第二行包含 n n n 个正整数，依次为 h 1 , h 2 , . . . h n h_1,h_2,...h_n h1,h2,...hn , 表示每个人的高度。

输出

输出留下的人数的最大值。

样例输入

5 5 3 2 1 2

样例输出

提示

对于所有数据， 1 ≤ n ≤ 1 0 6 , 0 ≤ h i ≤ 1 0 6 1≤n≤10^6,0≤h_i≤10^6 1≤n≤106,0≤hi≤106

#include <iostream> #include <cstdio> #include <cstring> #include <set> #include <queue> using namespace std; typedef long long ll; typedef pair<ll,ll>PII ; const int mod = 12345; const int inf = 0x3f3f3f3f; const int maxn = 1e4+10; int n,x,k=2,h,ans; inline void work() { scanf("%d", &n); scanf("%d", &x); for (int i = 1; i < n; i++) { scanf("%d", &h); if (h > x && k != 1) { ans++; k = 1; } if (h < x && k != 0) { ans++; k = 0; } x = h; } printf("%dn", ans + 1); } int main() { int T=1; //scanf("%d", &T); while (T--) { work(); } return 0; }