80分求助

P2249 【深基13.例1】查找

_1234y61 @ 2024-11-16 21:26:40

80分求大佬调😭😭😭 最后一个ted

#include <stdio.h>
int main()
{
    int n,m,i;
    scanf("%d %d",&n,&m);//n为数字个数,m为询问次数
    int num1[n];
    int num2[m];
    for(i=0;i<n;i++)
    {
        scanf("%d",&num1[i]);//数组
    }
    for(i=0;i<m;i++)
    {
        scanf("%d",&num2[i]);//要查询的数
    }
    int left=0;
    int right=n-1;
    int middle;
    int find;
    int temp;
    int count;
    for(i=0;i<m;i++)
    {
     count=0;
     left=0;
     right=n-1;
     find=num2[i];
    while(left<=right)
    {
        middle=(left+right)/2;
        if(num1[middle]>find)
        {
            right=middle-1;
        }else if(num1[middle]<find)
        {
            left=middle+1;
        }else
        {
            count++;
            temp=middle-1;
            while(1)
            {
                if(num1[temp]!=find||temp<0)
                {
                    break;
                }
                temp--;
            }
            printf("%d ",temp+1+1);
                break;
        }

    }
        if(count==0)
    {
        printf("-1 ");
    }
    }
    return 0;
}

by SDSXC @ 2024-11-17 12:44:02

在37~51行这一段,处理和要查找的数相等的数时一个一个找可能会在有很多相等的数时TLE

比如这样构造一组数据

1000000

1 1 1 1 1 1 …… 1

1 1 1 1 1 1 …… 1

就挂了

正确做法应该是在找到相等的数的时候做right=middle,然后继续查找,直到[left,right]缩减成只有一个数时得到答案


by _1234y61 @ 2024-11-17 20:10:18

@SDSXC 谢谢大佬 过了???


by hanfuyanhe123 @ 2024-11-22 22:23:18

/*
----11111...
  ----------i1iiii111####*
     ------------------iii1iii11111##*
      --------------------------i1iii1111111####***
            ||      88      88     ||
            ||     88        88    ||
            ||     _        _      ||
            ||    |,|      |,|     ||
           ||     [         ]      ||
           ||     [         ]      ||    为什么!!!!!!!!!!!
          ||      [         ]      ||
          ||          hh           ||
           ||         hh           ||
            ||    |        |       ||
            ||    I        I       ||
             ||    --------       ||
                ||              ||
88888888888888888888888888888888888888888888888888888*/

by stickfigures @ 2024-12-01 13:55:56

什么是ted


|