c语言#1WA #6TLE 求大佬帮改进

Kotori_Kawaii @ 2023-10-26 10:20:10

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int a[1000050];//n个数
int b[100050];//m次询问
int main()
{
    int n, m;//n个数 m次询问
    int left, right, mid;//左下标 右下标 中下标
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) 
        scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) 
        scanf("%d", &b[i]);
    for (int i = 0; i < m; i++) {
        left = 0,right = n - 1;
        while (left <= right) {
            mid = left - (left - right) / 2;
            if (a[mid] > b[i]) right = mid - 1;
            else if (a[mid] < b[i]) left = mid + 1; 
            else{
                while (a[mid]==b[i]) {//待优化
                    --mid;
                }
                break;
            }
        }
        if (b[i] - a[mid+1]) {
            printf("-1 ");
        }
        else {
            printf("%d ", mid + 2);
        }
    }
    return 0;
}

by Silvestorm @ 2023-10-26 12:19:25

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int a[1000050];//n个数
int b[100050];//m次询问
int main()
{
    int n, m;//n个数 m次询问
    int left, right, mid;//左下标 右下标 中下标
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) 
        scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) 
        scanf("%d", &b[i]);

    //改了这里  
    for (int i = 0; i < m; i++) {
        left = 0,right = n - 1;
        while (left < right)//当left==right时，结束循环
        {
            mid = (left + right) / 2;
            if (a[mid] >= b[i]) right = mid ;//将第三个if语句合并到这里，防止出现大量相当的数时，运行超时
            else if (a[mid] < b[i]) left = ceil((left*1.0+right)/2)//注意，类似于left=1,right=2，结果mid=1，可能导致死循环，用mid+1可能会答案错误，这里建议用ceil向上取整 ; 
        }
        if (b[i] - a[left]) {
            printf("-1 ");
        }
        else {
            printf("%d ", left+1);
        }//基于上一注释，这里用left判断。。。。。建议将二分查找封装为函数，后面给出我的模板

    }
    return 0;
}

int find(int t, int &a, int &b)

{

    if (t <= num[(a + b) / 2])
        b = (a + b) / 2;
    else
        a = ceil((a * 1.0 + b) / 2);

    if (a != b)
        return find(t, a, b);//进行下一步查找
    return a;

}//t为要查找的值，a为left，b为right，懒得改了
用法 
        cin >> s;

        int c=find(s,a,b);

        if(s==num[c])
         cout<<c+1<<" ";
        else cout<<"-1"<<" ";
 ``` cpp

by Kotori_Kawaii @ 2023-10-26 20:15:45

@Silvestorm 坏力，被薄纱了QAQ

by Kotori_Kawaii @ 2023-10-26 20:16:15

@Silvestorm 谢谢老哥qwq

by Kotori_Kawaii @ 2023-10-26 20:25:09

@Silvestorm 我测你这思路太好了 用递归来简化了QAQ

by Silvestorm @ 2023-10-26 22:36:16

@Kotori_Kawaii 递归也离你不远了呢