拼多多2020秋招3题

[MyLinChi]

问题

两集合A,B，每个集合中都是一个数对，从A，B中各选一个，使得第二个数的和大于T的情况下第一个数的和最小。

求解

用数组存储两集合，对第二个数排序便于查找符合条件的数对，对其中一个集合（选较大的）求出当前元素及其右边中元素的最小值。总体时间复杂度max(O(NlgN),O(MlgM))。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
using namespace std;
class Solution {
private:
    int N, M, T;
    int res = INT_MAX;
    vector<vector<int>> mid;
    vector<vector<int>> nig;
    
    static bool cmp(const vector<int>& a,const vector<int>& b) {
        return a[1] < b[1];
    }

    void inputNums(vector<vector<int>>& nums,int len) {
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < 2; ++j) {
                cin >> nums[i][j];
            }
            if (nums[i][1] >= T)res = min(res, nums[i][0]);
        }
    }

    int firstequalAndL(vector<vector<int>>& nums, int tar) {
        int i = 0, j = nums.size() - 1;
        for (; i <= j;) {
            int mid = i + ((j-i) >> 1);
            if (nums[mid][1] >= tar) {
                j = mid;
                if (i == j)break;
            }
            else
                i = mid + 1;
        }
        if (i > j)
            return -1;
        else
            return i;
    }

    void transferToMinValueFromRight(vector<vector<int>>& nums) {
        for (int i = nums.size() - 2; i >= 0; --i) {
            nums[i][0] = min(nums[i][0],nums[i + 1][0]);
        }
    }
public:
    void fun() {
        cin >> N >> M >> T;
        mid = vector<vector<int>>(N, vector<int>(2));
        nig = vector<vector<int>>(M, vector<int>(2));
        inputNums(mid, N);
        inputNums(nig, M);
        sort(mid.begin(), mid.end(), cmp);
        sort(nig.begin(), nig.end(), cmp);
        if (N > M) {
            transferToMinValueFromRight(mid);
            for (int i = 0; i < M; ++i) {
                int resT = T - nig[i][1];
                int ind = firstequalAndL(mid, resT);
                if (ind >= 0) {
                    res = min(res, nig[i][0] + mid[ind][0]);
                }
            }
        }
        else {
            transferToMinValueFromRight(nig);
            for (int i = 0; i < N; ++i) {
                int resT = T - mid[i][1];
                int ind = firstequalAndL(nig, resT);
                if (ind >= 0) {
                    res = min(res, mid[i][0] + nig[ind][0]);
                }
            }
        }
        cout << res << endl;
    }
};
int main() {
    Solution sol;
    sol.fun();
    return 0;
}