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

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

## 【HDU 5532 Almost Sorted Array】水题，模拟

helena_wang 2015-11-03 23:58:00 浏览388

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 }```

helena_wang
+ 关注