80份最后一个点TLE怎么回事？

lanmengfei @ 2023-06-01 21:39:06

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int MAXN=-1,n,a[maxn],c[maxn],h=2,m,k,cx=1000000000+5;
bool flag=0,flagg=0;
void find_(int l,int r,int a[],int k){
    if(l>r){
        return;
    }
    int id=(l+r)/2,mid=a[id];
    if(k!=mid and flagg==1){
        return;
    }
    if(k<mid){
        find_(l,id-1,a,k);
    } 
    if(k==mid){
        flag=1;
        flagg=1;
        cx=min(cx,id);
        find_(l,r-1,a,k);
    }
    if(k>mid){
        find_(id+1,r,a,k); 
    }
    return;
} 
int main(){
    scanf("%d%d",&n,&m);
    scanf("%d",&a[1]);
    c[1]=a[1];
    for(int i=2;i<=n;i++){
        scanf("%d",&a[i]);
        MAXN=max(MAXN,a[i]);
        if(a[i]!=a[i-1]){
            c[h]=a[i];
            h++;
        }
    }--h;
    for(int i=1;i<=m;i++){
        cin>>k;
        flag=0,flagg=0;
        cx=MAXN+1;
        find_(1,n,a,k);
        if(flag==1){
            cout<<cx<<" ";
        }
        else{
            cout<<-1<<" ";
        }
    }
    return 0;
} 

by _buzhidao_ @ 2023-06-01 21:55:32

@lanmengfei 我也求助，我20分。。。

by da_ke @ 2023-06-01 22:06:35

@lanmengfei 其实核心只有一个命令

int ans=lower_bound(a+1,a+n+1,x)-a;

by eastonwu @ 2023-06-01 22:12:53

@WA_Coding_Duck 连lower_bound都不用，普通的二分查找就可以做了。代码搁这了：

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,mid;
long long a[2000000];
int find(int k) 
//二分查找 
{
    int left=1,right=n;
    while (left<right)
    {
        mid=(right+left)/2;
        if (a[mid]>=k) 
        {
        right=mid;      
        }
        else 
        {
        left=mid+1;         
        }
    }
    if (a[left]==k) 
    {
    return left;    
    }
    else 
    {
    return -1;      
    }
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
    cin>>a[i];  
    }
    for (int i=1;i<=m;i++)
    {
        cin>>x;
        cout<<find(x)<<" ";
    }
    return 0;
}

自己找一下错误，不用写怎么复杂。

by ninji @ 2023-06-01 22:16:45

@eastonwu

#include <iostream>
const int N=1e6+5;
int a[N],m,n,q;
int find(int x)
{
    int l=1,r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(a[mid]==x) return mid;
        else if(a[mid]>x) r=mid-1;
        else l=mid+1;
     }
     return -1; 
}
using namespace std;
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
    {
        cin >> q;
        cout << find(q);
        cout <<" " ;
    }

    return 0;
}

为啥输出1 2 -1

by lanmengfei @ 2023-06-01 22:22:39

@eastonwu 行，我再看一下

by lanmengfei @ 2023-06-01 22:32:10

@eastonwu 想了一种新解法： 用数组c存储实际出现过的数（就是指去重） b来存储这些数第一次出现的地址 贴代码：（AC了！谢谢大佬！！！）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,a[maxn],c[maxn],b[maxn],h=2,m,k,cx;
bool flag=0;
void find_(int l,int r,int a[],int k){
    if(l>r){
        return;
    }
    int id=(l+r)/2,mid=a[id];
    if(k<mid){
        find_(l,id-1,a,k);
    } 
    if(k==mid){
        cx=id;
        flag=1;
        return;
    }
    if(k>mid){
        find_(id+1,r,a,k); 
    }
    return;
} 
int main(){
    scanf("%d%d",&n,&m);
    scanf("%d",&a[1]);
    c[1]=a[1];
    b[1]=1;
    for(int i=2;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]!=a[i-1]){
            c[h]=a[i];
            b[h]=i;
            h++;
        }
    }h--;
    for(int i=1;i<=m;i++){
        scanf("%d",&k);
        flag=0;
        find_(1,h,c,k);
        if(flag==1){
            printf("%d ",b[cx]);
        }
        else{
            printf("-1 ");
        }
    }
    return 0;
}