c - 在一组数字中找到最小值或最大值的计数

问题描述

用户在下一行输入n个要跟随的数据，然后输入n个数字a1，a2，...，an。这些数字是一些山脉的高度。如果只有一个最大值或最小值，则这些数字的集合是“可接受的”。例如“1 2 3 2 1”只有一个最大值，即 3。“1 2 3 4”也有一个最大值。但是“1 10 9 8 7 6 5 6 7”是不可接受的，因为它有两个最大值（10 和 7）或两个最小值（1 和 5）。

换句话说，当且仅当它是以下形式之一时，该集合是可接受的：

a1<=a2<=a3 ... <= ai > a(i+1) > ... >an

或者

a1>=a2>=a3 ... >= ai < a(i+1) < ... < an.

我必须在一个用未知测试用例测试它的法官系统中提交答案。完全禁止使用任何类型的数组或向量。

我的解决方案是这样的：

//C code.
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n,temp;
    scanf("%d",&n);
    if (n==1)
    {
        int l;
        scanf("%d",&l);
        printf("Yes");
    }
    else
{
    int a,b;
    int last;
    int changes =0;
    int dec =0 , inc =0; //flag: checking if the set is incremental or decremental till now
    scanf("%d %d",&a,&b);

    if (a>b)
    {
        dec=1;
    }
    else if (a<b)
    {
        inc = 1;
    }
    else
    {
        inc =1;
        dec = 1;
    }
    last = b;
    for (int i =2;i<n;i++)
    {

        scanf("%d",&temp);
        if (temp>last && dec==1)
        {
            inc = 1;
            dec= 0;
            changes++;
        }
        if (temp<last && inc==1)
        {
            inc =0;
            dec=1;
            changes++;
        }


if (!(inc==1 && dec==1) && temp == last)
        {
            changes++;
        }
    last = temp;
        last = temp;
    }
    if (changes <=1)
    {

        printf("Yes");
    }
    else
    {
        printf("No");
    }
}
    return 0;
}

它为问题中的示例获得正确答案，但在某些未知的测试用例中失败。知道如何解决这个问题吗？谁能给我一个在这段代码中没有解决的测试用例？

P.1：我添加了

if (!(inc==1 && dec==1) && temp == last)
    {
        changes++;
    }

它接受了一个失败的测试用例，但仍然存在一个。

P.2：

这是我的另一种算法，它在某些测试用例上失败，但法官接受了它对第一个失败测试用例的回答：

    #include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    int inc=0;
    int dec=0;
    int peak=0;
    int valley=0;
    int last = -1;
    int a;
    scanf("%d",&n);
    for (int i =0;i<n;i++)
    {
        if (last!=-1)
        {
            last =a;
        }
        scanf("%d",&a);
        if (last!=-1)
        {
            if (a>last)
            {
                if (!(inc==1))
                {
                    valley++;
                    inc =1;
                    dec=0;
                }
            }
            if (a<last)
            {
                if (!(dec==1))
                {
                    peak++;
                    dec=1;
                    inc =0;
                }
            }
        }
        last =0;


    }
    if (valley<=1 && peak<=1)
    {
        // printf("valley: %d , peak:%d",valley,peak);
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
}

P.3

新算法：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    long long int n,temp;
    scanf("%lld",&n);
    if (n==1)
    {
        long long int l;
        scanf("%lld",&l);
        printf("Yes");
    }
    else
{
    long long int a,b;
    long long int last;
    long long int changes =0;
    int dec =0 , inc =0; //flag: checking if the set is incremental or decremental till now
    scanf("%lld %lld",&a,&b);

    if (a>b)
    {
        dec=1;
    }
    else if (a<b)
    {
        inc = 1;
    }
    else
    {
        inc =1;
        dec = 1;
    }
    last = b;
    for (long long int i =2;i<n;i++)
    {

        scanf("%lld",&temp);
        if (temp>last && dec==1)
        {
            inc = 1;
            dec= 0;
            changes++;
        }
        if (temp<last && inc==1)
        {
            inc =0;
            dec=1;
            changes++;
        }
        if (changes>=1 && temp == last)//new change
        {
            changes+=100;
        }//end of new change
        last = temp;
    }
    if (changes <=1)
    {

        printf("Yes");
    }
    else
    {
        printf("No");
    }
}
    return 0;
}

标签： calgorithmminima

c - 在一组数字中找到最小值或最大值的计数

问题描述

解决方案

推荐阅读