天池 在线编程 最佳利用率（二分查找 + 哈希）

示例1
输入:
A = [1, 4, 6, 9], B = [1, 2, 3, 4], K = 9
输出: 
[2, 2]

示例2:
输入: 
A = [1, 4, 6, 8], B = [1, 2, 3, 5], K = 12
输出:
[2, 3]

class Solution {
public:
    /**
     * @param A: an integer sorted array
     * @param B: an integer sorted array
     * @param K: an integer
     * @return: return a pair of index
     */
    vector<int> optimalUtilization(vector<int> &A, vector<int> &B, int K) {
        // write your code here
        if(A.empty() || B.empty() || A[0]+B[0] > K) return {};
        unordered_map<int,int> m;
        for(int i = 0; i < B.size(); ++i)
            if(m.find(B[i]) == m.end())
                m[B[i]] = i;//每个数最早出现的位置
        int i = 0, j = B.size()-1, n1 = A.size(), n2 = B.size(), sum, maxsum=INT_MIN;
        vector<int> ans(2);
        for(int i = 0; i < n1; ++i)
        {
            int t = K-A[i];
            int l = 0, r = n2-1, pos=-1;
            while(l <= r)	// 二分查找
            {
                int mid = l+((r-l)>>1);
                if(B[mid] > t)
                    r = mid-1;
                else
                {
                    if(mid==n2-1 || B[mid+1] > t)
                    {
                        pos = mid;
                        break;
                    }
                    else
                        l = mid+1;
                }
            }
            if(pos != -1)
            {
                sum = A[i]+B[pos];
                if(sum > maxsum)
                {
                    maxsum = sum;
                    ans[0] = i;
                    ans[1] = m[B[pos]];
                }
            }
            else
                break;
        }
        return ans;
    }
};