Loading... # Singing Everywhere > **Baobao loves singing very much and he really enjoys a game called ***Singing Everywhere*, which allows players to sing and scores the players according to their performance. > **Consider the song performed by Baobao as an integer sequence **a_1, a_2,\dots,a_n**, where **a_i** indicates the ***i*-th note in the song. We say a note **a_k** is a "voice crack", if 1 < k < n,** a_{k-1} < a_k and a_{k+1} < a_k**. The more voice cracks BaoBao sings, the lower score he gets. > **To get a higher score, BaoBao decides to delete at most one note in the song. What's the minimum number of times BaoBao sings a voice crack after this operation?** #### Input > **There are multiple test cases. The first line of the input contains an integer T***T* (about 100), indicating the number of test cases. For each test case: > **The first line contains one integer n***n* (1 \leq n \leq 10^{5}1≤*n*≤105), indicating the length of the song. > **The second line contains n integers **a_1, a_2, \dots, a_n, (-2^{31} \leq a_i < 2^{31})**, indicating the song performed by BaoBao.** > **It's guaranteed that at most 5 test cases have n > 100.** #### Output > **For each test case output one line containing one integer, indicating the answer.** #### Sample Input ``` 3 6 1 1 4 5 1 4 7 1 9 1 9 8 1 0 10 2 1 4 7 4 8 3 6 4 7 ``` #### Sample Output ``` 1 0 2 ``` #### Hint > **For the first sample test case, BaoBao does not need to delete a note. Because if he deletes no note, he will sing 1 voice crack (the 4th note), and no matter which note he deletes, he will also always sing 1 voice crack.** > **For the second sample test case, BaoBao can delete the 3rd note, and no voice cracks will be performed. Yay!** > **For the third sample test case, BaoBao can delete the 4th note, so that only 2 voice cracks will be performed (4 ****8** 3 and 3 **6** 4). **翻译** > **宝宝非常喜欢唱歌，他真的很喜欢一款名为***“到处唱歌*”的游戏，该游戏允许玩家根据玩家的表现唱歌和得分。 > **将宝宝演唱的歌曲视为整数序列a**~1~,a~2~，...，a~n~，其中a~i~表示歌曲中的第 i个音符。我们说一个音符a~k~一个k是“语音破解”，如果1 < k < n, a~k-1~<a~k~和a~k+1~ < a~k~.宝宝唱的声音越裂，他得到的分数就越低。 **为了获得更高的分数，宝宝决定最多删除歌曲中的一个音符。在这次手术后，宝宝唱语音破解的最少次数是多少？** #### 输入 **有多个测试用例。输入的第一行包含一个整数T（约 100 个），表示测试用例的数量。对于每个测试用例：** **第一行包含一个整数n ** (1 \leq n \leq 10^{5}) **，指示歌曲的长度。** **第二行包含n整数** a_1、a_2、\dots a_n, (-2^{31} \leq a_i < 2^{31}−2^{31}≤a_i<2^{31}）**，表示宝宝演唱的歌曲。** **可以保证最多 5 个测试用例具有n > 100.** #### 输出 **对于每个测试用例，输出一行包含一个整数，指示答案。** #### 示例输入 ``` 3 6 1 1 4 5 1 4 7 1 9 1 9 8 1 0 10 2 1 4 7 4 8 3 6 4 7 ``` #### 示例输出 ``` 1 0 2 ``` #### 提示 **对于第一个示例测试用例，包宝不需要删除注释。因为如果他不删除音符，他会唱1个声音破解（第4个音符），无论他删除哪个音符，他也总是唱1个声音破解。** **对于第二个示例测试用例，Baobao可以删除第三个音符，并且不会执行语音破解。耶！** **对于第三个示例测试用例，宝宝可以删除第 4 个音符，以便仅执行 2 个语音破解（4 ****8** 3 和 3 **6** 4）。 **题解** **宝宝只能至多只能删除一个音符，用总共的破音减去删除一个音符后的破音就是我们要的结果，由题可知 ，一个峰顶即为一个破音** 1. **首先考虑当两个峰顶间只差一个音符的情况，如果两个峰顶值相等，去掉中间的音符后两个峰顶都会消失，即去掉了两个峰顶，否则就是一个** 2. **其次就是峰顶在第二个音符或在倒数第二个音符，去掉第一个音符或最后一个音符就可以使得峰顶消失** 3. **最后就是峰顶两侧的音符值相同，去掉峰顶的音符后该峰顶消失** ``` #include <iostream> #include <vector> using namespace std; typedef long long ll; const int maxn = 1e5 + 5; vector<int> vi; ll a[maxn]; int main(void) { int t; scanf("%d", &t); while (t --) { vi.clear(); int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); } for (int i = 2; i < n; ++i) { if (a[i] > a[i - 1] && a[i] > a[i + 1]) { vi.push_back(i); } } int cnt = 0; for (int i = 1; i < vi.size(); ++i) { int p = vi[i]; if (vi[i] - vi[i - 1] == 2) { if (a[p] == a[p - 2]) { cnt = 2; } else { cnt = max(cnt, 1); } } if (p==2 || p==n-1 || (p>1 && p<n && a[p-1]==a[p+1])) { cnt = 1; } } printf("%d\n", vi.size() - cnt); } return 0; } ``` **参考博客** [2019浙江省程序设计竞赛 H：Singing Everywhere（简单贪心）](http://t.csdn.cn/VK6As) 最后修改：2022 年 07 月 17 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏
