【HDU 5532 Almost Sorted Array】水题,模拟

  1. 云栖社区>
  2. 博客>
  3. 正文

【HDU 5532 Almost Sorted Array】水题,模拟

helena_wang 2015-11-03 23:58:00 浏览388
展开阅读全文

给出一个序列(长度>=2),问去掉一个元素后是否能成为单调不降序列或单调不增序列。

对任一序列,先假设其可改造为单调不降序列,若成立则输出YES,不成立再假设其可改造为单调不增序列,若成立则输出YES,不成立则输出NO。

由于持平不影响整体单调性,为了直观,我在以下把“不降”称为“递增/升序”,把“不增”称为“递减/降序”。

递增和递减是对称的,这里先考虑递增,递减改个符号和最值就好。

我们把为维护单调性而去掉的那个点称为“坏点”。由题目的要求,“可改造”可等价于“只存在一个坏点”。

对于“坏点”的判断,我们可以先找出是否只存在一组“逆序”。

对于“almosted sorted”递增序列,只存在一组逆序无非以下四种情况(这里先不考虑逆序在边界)。

现在考虑逆序在边界的情况。由于a[]数组元素下标是1~n,而此题1<=ai<=100000,那么对于递增序列,可把a[0]设为1、把a[n+1]设为100000作为首尾哨兵节点,一定不会破坏整体单调性;递减序列做对称的处理。这样边界也可以像中间一样处理。

由于三种情况满足一种即可,而第二种可以看作第三种和第四种的交集,故只需按照第三种和第四种的情况对a[]数组各进行一次遍历,满足一种即可输出YES。

对于坏点的处理,我们采用“当它不存在”的策略,所以首次遇到坏点,忽略它,再次遇到坏点,则此种情况不成立。

至于如何由“逆序”推出“坏点”,并实现几种情况的判断,我们遍历i:0~n,对于第一对逆序a[i]>a[i+1],我们可以:

先采取“左归”(第三种),即把a[i]当作坏点,判断a[i-1]和a[i+1]是否升序(若不升序则相当于构成了第二对逆序,出现第二个坏点);

若左归不成立,再采取“右归”(第四种),即把a[i+1]当坏点,同理判断a[i]和a[i+2]是否升序。

11.23更新代码如下,更加简化,速度更快

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 const int MAX_N=100005;
 5 const int MIN_A=1;
 6 const int MAX_A=100000;
 7 int T;
 8 int n;
 9 int a[MAX_N];
10 int flag;
11 int fix_cnt;
12 
13 int main()
14 {
15     freopen("5532.txt","r",stdin);
16     scanf("%d",&T);
17     while(T--)
18     {
19         scanf("%d",&n);
20         for(int i=1;i<=n;i++)
21         {
22             scanf("%d",&a[i]);
23         }
24         //升序
25         flag=1;//假设去掉最多一个元素后整体降序
26         fix_cnt=0;
27         a[0]=MIN_A;
28         a[n+1]=MAX_A;
29         for(int i=1;i<=n-1;i++)
30         {
31             if(a[i]<=a[i+1]) continue;
32             fix_cnt++;
33             if(fix_cnt<=1&&(a[i-1]<=a[i+1]||a[i]<=a[i+2])) continue;
34             flag=0;
35             break;
36         }
37         if(flag)
38         {
39             printf("YES\n");
40             continue;
41         }
42         //降序
43         flag=1;//假设去掉最多一个元素后整体降序
44         fix_cnt=0;
45         a[0]=MAX_A;
46         a[n+1]=MIN_A;
47         for(int i=1;i<=n-1;i++)
48         {
49             if(a[i]>=a[i+1]) continue;
50             fix_cnt++;
51             if(fix_cnt<=1&&(a[i-1]>=a[i+1]||a[i]>=a[i+2])) continue;
52             flag=0;
53             break;
54         }
55         if(flag)
56         {
57             printf("YES\n");
58             continue;
59         }
60         printf("NO\n");
61     }
62     return 0;
63 }

先前版本代码如下:

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 const int MAX_N=100005;
 5 const int MIN_A=1;
 6 const int MAX_A=100000;
 7 int T;
 8 int n;
 9 int in[MAX_N],de[MAX_N];
10 int flag;
11 int fix_cnt;
12 
13 int main()
14 {
15     freopen("5532.txt","r",stdin);
16     scanf("%d",&T);
17     while(T--)
18     {
19         scanf("%d",&n);
20         for(int i=1;i<=n;i++)
21         {
22             scanf("%d",&in[i]);
23             de[i]=in[i];
24         }
25 
26         //升序的情况
27         in[0]=MIN_A;
28         in[n+1]=MAX_A;
29         flag=1;//假设去掉最多一个元素后整体升序
30         fix_cnt=0;
31         for(int i=1;i<=n-1;i++)
32         {
33             if(in[i]<=in[i+1]) continue;
34             fix_cnt++;//左归的情况
35             if(fix_cnt<=1&&in[i-1]<=in[i+1]) continue;
36             flag=0;
37             break;
38         }
39         if(flag)
40         {
41             printf("YES\n");
42             continue;
43         }
44         flag=1;
45         fix_cnt=0;
46         for(int i=1;i<=n-1;i++)
47         {
48             if(in[i]<=in[i+1]) continue;
49             fix_cnt++;//右归的情况
50             if(fix_cnt<=1&&in[i]<=in[i+2]) continue;
51             flag=0;
52             break;
53         }
54         if(flag)
55         {
56             printf("YES\n");
57             continue;
58         }
59         //降序的情况
60         de[0]=MAX_A;
61         de[n+1]=MIN_A;
62         flag=1;//假设去掉最多一个元素后整体降序
63         fix_cnt=0;
64         for(int i=1;i<=n-1;i++)
65         {
66             if(de[i]>=de[i+1]) continue;
67             fix_cnt++;//左归的情况
68             if(fix_cnt<=1&&de[i-1]>=de[i+1]) continue;
69             flag=0;
70             break;
71         }
72         if(flag)
73         {
74             printf("YES\n");
75             continue;
76         }
77         flag=1;
78         fix_cnt=0;
79         for(int i=1;i<=n-1;i++)
80         {
81             if(de[i]>=de[i+1]) continue;
82             fix_cnt++;//右归的情况
83             if(fix_cnt<=1&&de[i]>=de[i+2]) continue;
84             flag=0;
85             break;
86         }
87         if(flag)
88         {
89             printf("YES\n");
90             continue;
91         }
92         printf("NO\n");
93     }
94     return 0;
95 }

 

网友评论

登录后评论
0/500
评论
helena_wang
+ 关注