Almost Sorted Array ---- UVALive

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5200

We are all familiar with sorting algorithms: quick sort, merge sort, heap sort, insertion sort, selection sort, bubble sort, etc. But sometimes it is an overkill to use these algorithms for an almost sorted array. We say an array is sorted if its elements are in non-decreasing order or non-increasing order.

We say an array is almost sorted if we can remove exactly one element from it, and the remaining array is sorted. Now you are given an array a1, a2, . . . , an, is it almost sorted?

Input

The first line contains an integer T indicating the total number of test cases. Each test case starts with an integer n in one line, then one line with n integers a1, a2, . . . , an.

• 1 ≤ T ≤ 2000

• 2 ≤ n ≤ 105

• 1 ≤ ai ≤ 105

• There are at most 20 test cases with n > 1000.

Output

For each test case, please output ‘YES’ if it is almost sorted. Otherwise, output ‘NO’ (both without quotes).

Sample Input

2 1 7

3 2 1

3 1 4 1 5

Sample Output

YES

题意

去掉一个数使得该序列单调递增或单调递减

思路

从第二位开始记录大于前面数字的数字个数小于前面数字的数字的个数

以及第一个大于前面数字的数字位置第一个小于前面数字的数字位置

个数小于等于1的那个可视为另类只要判断去掉这个位置的数字或者去掉其前一项能否使得序列单调即可


  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 int main()
  5 {
  6     int t, n, a[100005];
  7     int i, num1, num2, i1, i2, temp;
  8     scanf("%d", &t);
  9     while(t--)
 10     {
 11         scanf("%d", &n);
 12         for(i=0; i<n; i++)
 13         {
 14             scanf("%d", &a[i]);
 15         }
 16 
 17         if(n<=3)
 18         {
 19             printf("YES
");
 20             continue;
 21         }
 22 
 23         num1 = 0;
 24         num2 = 0;
 25         for(i=2; i<n; i++)
 26         {
 27             if(a[i]>a[i-1])
 28             {
 29                 if(num1==0) i1 = i;
 30                 num1++;
 31             }
 32             else if(a[i]<a[i-1])
 33             {
 34                 if(num2==0) i2 = i;
 35                 num2++;
 36             }
 37         }
 38         if(num1==0||num2==0)
 39         {
 40             printf("YES
");
 41             continue;
 42         }
 43 
 44         num1 = 0;
 45         num2 = 0;
 46         for(i=1; i<n; i++)
 47         {
 48             if(a[i]>a[i-1])
 49             {
 50                 if(num1==0) i1 = i;
 51                 num1++;
 52             }
 53             else if(a[i]<a[i-1])
 54             {
 55                 if(num2==0) i2 = i;
 56                 num2++;
 57             }
 58         }
 59 
 60         if(num1<=1||num2<=1)
 61         {
 62             if(num2<=1)
 63             {
 64                 if(i2-1>0)
 65                 {
 66                     temp = a[0];
 67                     for(i=1; i<n; i++)
 68                     {
 69                         if(i==i2-1) continue;
 70                         if(a[i]<temp) break;
 71                         temp = a[i];
 72                     }
 73                     if(i>=n)
 74                     {
 75                         printf("YES
");
 76                         continue;
 77                     }
 78                 }
 79 
 80 
 81                 temp = a[0];
 82                 for(i=1; i<n; i++)
 83                 {
 84                     if(i==i2) continue;
 85                     if(a[i]<temp) break;
 86                     temp = a[i];
 87                 }
 88                 if(i>=n)
 89                 {
 90                     printf("YES
");
 91                     continue;
 92                 }
 93 
 94             }
 95             if(num1<=1)
 96             {
 97                 if(i1-1>0)
 98                 {
 99                     temp = a[0];
100                     for(i=1; i<n; i++)
101                     {
102                         if(i==i1-1) continue;
103                         if(a[i]>temp) break;
104                         temp = a[i];
105                     }
106                     if(i>=n)
107                     {
108                         printf("YES
");
109                         continue;
110                     }
111                 }
112 
113                 temp = a[0];
114                 for(i=1; i<n; i++)
115                 {
116                     if(i==i1) continue;
117                     if(a[i]>temp) break;
118                     temp = a[i];
119                 }
120                 if(i>=n)
121                 {
122                     printf("YES
");
123                     continue;
124                 }
125             }
126             printf("NO
");
127         }
128         else printf("NO
");
129     }
130     return 0;
131 }