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

Question

用户在下一行输入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;
}

score 3 · Accepted Answer

scanf("%d",l);应该是scanf("%d", &l);，scanf需要变量的地址。

所以测试用例n == 1失败了。

始终查看编译器警告：https ://ideone.com/MKq3WK

score 2 · Accepted Answer

“4 1 1 2 1”说“不”，但应该说“是”。代码不能正确处理最初都是 1inc的情况。dec

此外，代码必须对序列的第一部分（直到观察到第一个方向变化）和第二部分使用不同的标准。在第一部分，平等是允许的，不会导致任何取消资格或状态改变。在第二部分，平等是不合格的。

玩笑

我不应该这样做，但有时无法抗拒。以下应该可以解决问题。不要使用它。

#include <stdio.h>

int main(void)
{
    int c, n, p, s;
    scanf("%d%d", &n, &c);

    #define Table   \
        {  1,  0,  3 }, \
        {  1,  1,  2 }, \
        { -1, -1,  2 }, \
        {  4,  3,  3 }, \
        {  4, -1, -1 }, \

    for (s = 0; 0 <= s && --n; s = (int [][3]) {Table} [s] [1+(p>c)-(p<c)])
        { p = c; scanf("%d", &c); }

    printf("%s\n", 0 <= s ? "Yes" : "No");
}

score 1 · Accepted Answer

我们必须检测不等式方向的变化，然后不允许进一步的变化。无论如何，只要元素相等，您就无法在增加或减少之间做出决定。

我将使用具有六个可能值的状态变量：

x：尚未输入任何元素；
0: 我们什么都不知道；
1：我们处于初始融资阶段；
-1：我们处于初始下降段；
2：我们在最后的加注部分；
-2: 我们在最后的下降部分。

考虑到先前和当前的输入值，以下转换适用：

State  x: -> 0 (unconditionally)
State  0: p < c ->  1, p > c -> -1
State  1: p > c -> -2
State -1: p < c ->  2
State  2: p >= c -> Fail
State -2: p <= c -> Fail

初始状态为x。如果我们从不失败，则在输入用尽时假定成功。这可以通过一个简单的 switch 语句和两个静态变量来实现，以记住先前的值和状态。

规范不清楚某些部分是否可以为空，所以我将保持原样。

Python 概念证明：

Input= [1, 2, 3, 2, 1]
#Input= [1, 10, 9, 8, 7, 6, 5, 6, 7]
#Input= [1, 2, 3, 4]
#Input= [4, 1, 2, 1, 1]

def Process(c):
    global p, s

    if s == None:
        s= 0
    elif s == 0:
        if p < c:
            s= 1
        elif p > c:
            s= -1
    elif s == 1:
        if p > c:
            s= -2
    elif s == -1:
        if p < c:
            s= 2
    elif s == 2:
        if p >= c:
            exit(-1)
    elif s == -2:
        if p <= c:
            exit(-1)
    p= c

s= None
for c in Input:
    Process(c)

score 1 · Accepted Answer

使用 P.2 解决方案，“4 1 2 1 1”被接受，但它不应该被接受，因为 1 不大于 1！

score 0 · Accepted Answer

The judge finally accepted this code. The main problems was with the conditions were some numbers get equal like 111222. Also the problem statement was right and it was not <= or >= after the ai.

Code in C:

#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;
    int flag =1;
    long long int changes =0;
    int incr=0,decr=0;
    int equ=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
    {
        equ=1;
    }
    last = b;
    for (long long int i =2;i<n;i++)
    {

        scanf("%lld",&temp);
        if (temp > last && equ==1)
        {
            inc = 1;
            dec=0;
            equ=0;
        }
        else if (temp <last && equ==1)
        {
            inc = 0;
            dec = 1;
            equ= 0;
        }
       else if (temp>last && dec==1)
        {
            inc = 1;
            dec= 0;
            changes++;
            incr++;
        }
        else if (temp<last && inc==1)
        {
            inc =0;
            dec=1;
            changes++;
            decr++;
        }
        if (changes>=1 && temp == last && incr>=0 && decr >=0)
        {
            flag = 0;
            changes+=100;
        }
        last = temp;
    }
    if (changes <=1&& flag)
    {

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

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

5 回答 5

玩笑

Related

Reference