本文主要是介绍【HDU】 5532 Almost Sorted Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Almost Sorted Array
- 链接
HDU 题目链接
- 题解
这题主要的思想就是运用前缀和后缀数组，判断删去一个之后剩余的部分是否是有序的。满足就是YES，没有一个满足就是NO。
第一次用这个编辑器写，感觉怪怪的…
- 代码
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;int T,n,a[100005],pre1[100005],sim1[100005],pre2[100005],sim2[100005];int main()
{scanf("%d",&T);while (T--){memset(a,0,sizeof(a));memset(pre1,0,sizeof(pre1));memset(sim1,0,sizeof(sim1));memset(pre2,0,sizeof(pre2));memset(sim2,0,sizeof(sim2));scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);pre1[0]=1; pre2[0]=1; pre1[1]=1; sim1[n]=1; pre2[1]=1; sim2[n]=1;sim1[n+1]=1; sim2[n+1]=1;for (int i=2;i<=n;i++){if (a[i]>=a[i-1] && pre1[i-1]) pre1[i]=1;if (a[i]<=a[i-1] && pre2[i-1]) pre2[i]=1;}for (int i=n-1;i>=1;i--){if (a[i]<=a[i+1] && sim1[i+1]) sim1[i]=1;if (a[i]>=a[i+1] && sim2[i+1]) sim2[i]=1;}int f=0;for (int i=2;i<=n-1;i++){if (pre1[i-1] && sim1[i+1] && a[i+1]>=a[i-1]) f=1;if (pre2[i-1] && sim2[i+1] && a[i-1]>=a[i+1]) f=1;}if (sim1[2] || sim2[2]) f=1;if (pre1[n-1] || pre2[n-1]) f=1;if (f) printf("YES\n");else printf("NO\n");}return 0;
}
这篇关于【HDU】 5532 Almost Sorted Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
