军训
时间： 3ms 内存：128M
描述：
有N 个军训新学员开始了他们的军训生活，第一天教官教他们站队，根据他们的身高，站成“凸”字形或者“凹”字形，也就是从左到右身高依次递增再递减或者依次递减再递增，如果是“凸”字形队列，身高最高的人可以有一个或者多个，其他人必须严格递增或或者递减，同样地，如果是“凹”字形队列，身高最矮的人可以有一个或者多个，其他人必须严格递增或者递减，现在这N 个同学已经站好了队，请你来判断一下现在这个队形是否是“凸”的或者“凹”的，如果是即输出YES，否则输出NO。
输入：
一个整数T(T<=50)表示数据组数，接下来每组数据包含两部分，首先是一个整数N(N<=100000)，表示人数，然后下一行N 个整数，表示每个人的身高h(h<=100000)。
输出：
对于每组数据，如果队列是“凸”的或者“凹”的，则输出YES，否则输出NO。
示例输入：
5
5
1 2 3 2 1
5
3 2 1 2 3
5
1 1 2 1 1
5
1 2 3 4 5
5
5 4 3 2 1示例输出：
YES
YES
NO
NO
NO
提示：
参考答案（内存最优[1240]）：
#include<stdio.h>
int main()
{
int T,N,a[100000]= {0},b,c,d;
scanf("%d",&T);
for(int i=1; i<=T; i++)
{
b=c=d=0;
scanf("%d",&N);
for(int j=1; j<=N; j++)
scanf("%d",&a[j]);
if(a[1]<a[2])//凸
{
c=a[2];
d=2;
for (int p=1; p<=N; p++)
{
if(a[p]>c)
{
c=a[p];
d=p;
}
} //找到 第d个数为最大值c
if(d==N) b++;
for(int q=1; q<d; q++)
{
if(a[q]>a[q+1] || (a[q]==a[q+1] && a[q]!=c) )
b++;
}
for(int v=N; v>d; v--)
{
if(a[v]>a[v-1] || (a[v]==a[v-1] && a[v]!=c))
b++;
}
}
else if(a[1]>a[2])//凹
{
c=a[2];
d=2;
for (int x=1; x<=N; x++)
{
if(a[x]<c)
{
c=a[x];
d=x;
}
} //找到 第d个数为最小值c
if(d==N) b++;
for(int y=1; y<d; y++)
{
if(a[y]<a[y+1] || (a[y]==a[y+1] && a[y]!=c))
b++;
}
for(int z=N; z>d; z--)
{
if(a[z]<a[z-1] || (a[z]==a[z-1] && a[z]!=c))
b++;
}
}
else
b++;
if(b==0)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
参考答案（时间最优[268]）：
#include<stdio.h>
int main()
{
int T,i,j,z,k;
long int n;
int x[100001];
scanf("%ld",&n);
for(j=1; j<=n; j++)
{
scanf("%d",&z);
for(i=1; i<=z; i++)
scanf("%d",&x[i]);
if(x[1]>x[2])
{
for(i=1;i<z;i++)
if(x[i]<x[i+1])
{
k=i;
break;
}
for(i=k;i<z;i++)
if(x[i]>=x[i+1])
{
break;
}
if(i==z&&x[z-1]<x[z])
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
else if(x[1]<x[2])
{
for(i=1;i<z;i++)
if(x[i]>x[i+1])
{
k=i;
break;
}
for(i=k;i<z;i++)
if(x[i]<=x[i+1])
{
break;
}
if(i==z&&x[z-1]>x[z])
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
else
{
printf("NO\n");
}
}
return 0;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。