不能用多线程吗？

eeley @ 2024-11-13 23:34:08

#include<iostream>
#include<vector>
#include<thread>
using namespace std;

atomic_int Tcount = 0;

void tfind(const vector<int>& source, const int findvalue, int& ret) {
    int t = lower_bound(source.begin(), source.end(), findvalue) - source.begin();
    if (findvalue == source[t])ret = t + 1;
    else ret = -1;
    Tcount++;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int m, n;
    cin >> m >> n;
    vector<int> prime;
    vector<int> ret(n, 0);
    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        prime.push_back(t);
    }
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        thread(tfind, cref(prime), a, ref(ret[i])).detach();
    }
    while (Tcount != n);
    for (auto it : ret) {
        cout << it << " ";
    }
}

by sdjjdjdjdjd @ 2024-11-13 23:42:41

不能，不要投机取巧。

你都用lower_bound了还开多线程？

by Ruiqun2009 @ 2024-11-13 23:44:37

@sdjjdjdjdjd 如果想在 O(n+m\log n) 的复杂度下减小常数似乎只有这种做法。

@eeley 这题有 O(n+m) 的做法。

by niuniudundun @ 2024-11-13 23:46:47

@eeley 你没有 return 0;。

by Ruiqun2009 @ 2024-11-13 23:50:32

@niuniudundun 都到本站了，return 0 其实对程序也没有影响了。

by Vector_Li @ 2024-11-14 07:52:35

@Ruiqun2009 ？教个 \Theta(n + q)？

by imzfx_Square @ 2024-11-14 08:13:08

@Vector_Li 可以离线处理的说。

by smzxyyc @ 2024-11-15 08:52:56

不能用二分吗？

#include<bits/stdc++.h>
using namespace std;
const int m1=1000005,m2=100005;
int a[m1],b[m2],maxn=INT_MIN;
int search(int a[],int l,int r,int k){  
    int mid;
    while(l<=r){
        mid=l+(r-l)/2;
        if(a[mid]>=k){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    if(a[l]==k){
        return l;
    }
    else{
        return -1;
    }
}
int main(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxn=max(maxn,a[i]);
    }
    for(int i=1;i<=q;i++){
        cin>>b[i];
        if(b[i]>=maxn){
            cout<<"-1 ";
            continue;
        }
        cout<<search(a,1,n,b[i])<<" ";
    }
    return 0;
}

100pts