求第 K 个总和值

Question

描述

给定两个大小为 N 的数组 A 和大小为 M 的 B 以及一个整数 K。创建一个大小为 N*M 的新数组 C，其中包含 A[i]+B[j]，其中 1≤i≤N，1≤j≤ M。找到数组 C 中第 K 个最小的元素。

输入格式

第一行包含T，测试用例的数量（1<=T<=10000).

第一行包含 3 个空格分隔的整数 N、M、K，其中 1<=N<=10^6, 1<=M<=10^6, 1<=K<=N*M.

下一行包含 N 个空格分隔的整数 (0<=Ai<=1e4).

下一行包含 M 个空格分隔的整数 (0<=Bi<=1e4).

所有测试用例的 min(N, M) 之和<=10^5.

输出格式

对于每个测试用例，打印数组 C 中的第 K 个最小元素。

我的这个问题超出了时间限制。这是我的解决方案：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int check2(vector<int> arr, int mid, int ele){
    if(arr[mid]>ele){
        return 1;
    }
    return 0;
}
int check(vector<int> arr, int n, vector<int> brr,int m, int ele, int k){
    int count = 0;
    for(int i=0;i<n;i++){
        int start = 0, end = m-1, ans = m;
        while(start<=end){
            int mid = start + (end-start)/2;
            if(check2(brr,mid, ele - arr[i]) == 1){
                ans = mid;
                end = mid-1;
            }else{
                start = mid+1;
            }
        }
        count = count + ans;
        //count = count + ( ( upper_bound(brr.begin(), brr.end(), ele - arr[i]) ) - brr.begin() );
    }
    if(count>=k){
        return 1;
    }
    return 0;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,m,k;
        cin>>n>>m>>k;
        vector<int> arr(n);
        vector<int> brr(m);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        for(int j=0;j<m;j++){
            cin>>brr[j];
        }
        
        sort(arr.begin(), arr.end());
        sort(brr.begin(), brr.end());
        /*
        if(n>m){
            swap(n,m);
            swap(arr,brr);
        }
        */
        int low = 0, high = arr[n-1] + brr[m-1], ans = -1;
        while(low<=high){
            int mid = low + (high-low)/2;
            if(check(arr,n,brr,m,mid,k)==1){
                ans = mid;
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

任何人都可以帮我解决我做错的地方吗？

Answer 1

您在这里犯的两个最大错误：在不需要时按值传递大型容器，并在执行时间至关重要时创建过多的调用和转换开销。

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using std::vector;
using std::cin;
using std::cout;
using std::endl;

inline bool check2( const vector<int64_t>& arr, int64_t mid, int64_t ele){
    return arr[mid] > ele;
}

inline bool check( const vector<int64_t>& arr, int n,
            const vector<int64_t>& brr,int64_t m, int64_t ele, int64_t k){
    int64_t count = 0;
    for(int64_t i = 0; i<n; i++){
        int64_t start = 0, end = m-1, ans = m;
        while(start <= end) {
            int64_t mid = start + (end-start)/2;
            if(check2(brr, mid, ele - arr[i]) ){
                ans = mid;
                end = mid-1;
            }else{
                start = mid+1;
            }
        }
        count = count + ans;
    }
    return  count >= k;
}

取决于所使用的编译器，令人厌恶的代码在模板代码上不起作用，并且这一切都会变成强制转换和溢出混乱。