题解
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int map[100005];
int book[100005];
#define inf 0x3f3f3f3f
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
int answer=0;
int flag=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&map[i]);
}
map[0]=inf;
memset(book,0,sizeof(book));
for(int i=2;i<n;i++){
if(map[i]>map[i-1]&&map[i]>map[i+1]){
answer++;
//连续的情况
if(book[i-1]==1){
//这时能减少两个破音
if(map[i-2]==map[i]){
flag=2;
}
//否则最少也能减少一个破音
else{
if(flag<2)
flag=1;
}
}
//不连续的情况
//这时候一个破音也减不了
if(map[i]>map[i-2]&&map[i]>map[i+2]&&( (map[i-1]>map[i-2]&&map[i-1]>map[i+1]) || (map[i+1]>map[i-1]&&map[i+1]>map[i+2]) ) ){
if(flag<1){
flag=0;
}
}
//其他情况都能减少一个破音
else{
if(flag<2)
flag=1;
}
book[i]=1;
book[i-1]=1;
book[i+1]=1;
}
}
printf("%d
",answer-flag);
}
return 0;
}
这道题大概意思就是说给一串序列，当(a_{i}>a_{i-1}并且a_{i}>a_{i+1}) 的时候，称这种情况为一个破音，让你只减少一个元素后，破音的最少数量是多少
通过分析可以发现，一共只有3种情况，我们只能减少2个破音，减少一个破音，还有不能减少破音的。
下面分情况讨论
1、能减少两个破音的情况
例子：
1 9 1 9 8 1 0
首先遍历一下，发现共有两个破音，但当我们删除第3位（从1开始计数）的1之后，序列变成1 9 9 8 1 0，此时一个破音也没有。我们可以归纳出这种情况的特征
- 两个破音必须相连
- 破音中间的数字相同
如果破音中间的数字不相同的话，那么一定能减少1个破音，证明：
如果两个破音中间的数字不相同，那么一定有大小关系，如果左边的大，例如1 9 1 7 6 1 0，那么删除第3位的1可减少1个破音，如果右边的大，例如1 6 1 9 6 1 0，仍然可以靠删除第3位的1来减少一个破音。
2、一次破音也减少不了的情况
例如：1 1 4 5 1 4
在这个序列中，破音是4 5 1，然而我们不论怎么删除，都不能减少破音，这种情况的条件是比较苛刻的，我们假设一段序列 a b c d e,其中b c d是破音，那么c必须要大于a和e，然后，还需要满足一个条件，那就是，b大于a和d或者d大于b和e 其中一个条件满足就行。
满足上述条件的话，是一次破音也减少不了的。
3、能减少一次破音的情况
除上述两种情况之外的情况都是能减少一次破音的。
在程序中，我用book数组标记破音，用来识别连续的破音。