binarySearch
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int binarySearch(vector<int>arr, int lo, int hi, int target){
  4.         if (lo > hi) {
  5.         return -1;
  6.     }
  7.     int mid = lo + ((hi - lo) >> 1);
  8.     if (arr[mid] == target && (arr[mid + 1] > target || mid == arr.size() - 1)) {
  9.         return mid;
  10.     } else if (arr[mid] < target || arr[mid] == target) {
  11.         return binarySearch(arr, mid + 1, hi, target);
  12.     } else {
  13.         return binarySearch(arr, lo, mid - 1, target);
  14.     }
  15. }
  16. int solve(vector<int>a, vector<int>b, vector<int>c, vector<int>d, int k){
  17.         map<int,int>mp;
  18.         int ans=0;
  19.         vector<int>tot;
  20.         for(int i=0;i<a.size();i++){
  21.                 for(int j=0;j<b.size();j++){
  22.                         int val=a[i]+b[j];
  23.                         tot.push_back(val);
  24.                 }
  25.         }
  26.         sort(tot.begin(),tot.end());
  27.         for(int i=0;i<c.size();i++){
  28.                 for(int j=0;j<d.size();j++){
  29.                         int target=k-c[i]-d[j];
  30.                         int idx= binarySearch(tot,0,tot.size()-1, target);
  31.                         ans=ans+(idx==-1 ? 0 : idx+1);
  32.                 }
  33.         }
  34.         return ans;
  35. }
  36. int main() {
  37.         vector<int>a{2,3},b{4},c{2,3},d{1,2};
  38.         cout<<solve(a,b,c,d,10)<<"n";
  39.         return 0;
  40. }
Parsed in 0.010 seconds