题目链接：点我
题意：给定一个序列，询问是否能删除一个数让它成为非递减或者非递增的序列。
比如说 删除后的序列是1 3 3 5 或者5 3 3 1 或者1 3 5 或者5 3 1 都可以。只要满足删掉某个数，构成非递减或者非递增，就输出YES，如果不能就输出NO
正解（LIS求最长上升子序列）：
正着来一遍，反着来一遍 注意要用upper_bound即可：
代码：
#include<bits/stdc++.h>
using namespace std;
int Maxlen(int a[],int n){
int b[];
memset(b,,sizeof(b));
int len = ;
for(int i = ; i < n; i ++)
{
if(len == ||a[i] >= b[len - ])
{
b[len] = a[i];
len ++;
}
else
{
int p = upper_bound(b,b + len,a[i]) - b;
b[p] = a[i];
}
}
return len;
}
int main(){
int t,n;
for(scanf("%d",&t);t--;){
scanf("%d",&n);
int a[],c[];
for(int i = ; i < n ; i++){
scanf("%d",&a[i]);
c[n-i-] = a[i];
}
int len = Maxlen(a,n);
int len1 = Maxlen(c,n);
if(len >= n- || len1 >= n-)puts("YES");
else puts("NO");
}
}
如果想瞎搞也行。。。
因为删除一个嘛，先证明删除一个能不能是非递减的（非递增的把序列倒过来搞一次就行了）
首先，对一个序列前后两个数做差
比如说序列
3 1 4 1 5 做差后（即1-3,4-1,1-4,5-1）是 -2,3，-3,4。发现有2个负数，那就不行。
如果序列是 3 1 1 5。 做差后是-2,0，4。发现有一个负数，是在头部，可以删掉
如果序列是5 6 3 ,7 7，做差后是 1，-3,4,0。发现有一个负数，而且可以跟左右两边的某个数相加变成正数，那么这个3就可以删掉。
如果序列是1 2 3 4，做差后是1,1,1,1 没有负数，本身就可以是非递减。
能看得出来：
做差后的序列：如果有2个及以上负数，那它肯定不可能是非递减。
如果有一个负数，它在头或者尾，或者在中间而且可以跟左右两边任意一个数相加是正数，即可以是非递减
如果没有负数，已经是非递减
时间复杂度是O（N），额外需要O（N）的空间存做差后的数组
非递增的话就把数组倒一下再来一次就行了。
代码（很乱）：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset> using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)
#define REP(i, x, n) for(int i = x; i <= n; ++i)
int main(){
int t,n;
for(scanf("%d",&t);t--;){
scanf("%d",&n);
int a[],b[],c[];
for(int i = ; i < n ; i++){
scanf("%d",&a[i]);
c[n-i-] = a[i];
}
int f1 = ,ard = -;
int s1 = ,s2 = ;
for(int i = ; i < n ; i++){
b[i] = a[i] - a[i-];
if(b[i] < ){
f1++;
ard = i;
}
if(f1 == ){
break;
}
}
if(f1 == ){
s1 = ;
}
if(f1 == ){
if(ard == || ard == n-){
s1 = ;
}
else if(b[ard] + b[ard-] >= || b[ard] + b[ard+] >= ){
s1 = ;
}
}
f1 = ;
ard = -;
//for(int i = 0 ; i < n ; i++) printf("%d ",c[i]);
for(int i = ; i < n ; i++){
b[i] = c[i] - c[i-];
if(b[i] < ){
f1++;
ard = i;
}
if(f1 == ){
break;
}
}
if(f1 == ){
s2 = ;
}
if(f1 == ){
if(ard == || ard == n-){
s2 = ;
}
else if(b[ard] + b[ard-] >= || b[ard] + b[ard+] >= ){
s2 = ;
}
}
s1||s2?puts("YES"):puts("NO");//s1,s2分别代表在非递减和非递增可不可以满足条件
}
}