军训

军训

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注