Advertisement
FuFsQ

I

Sep 30th, 2018
309
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. int bf(vector<int> &c, int val){
  7.     int L = 0, R = c.size(), middle, dt = 9999999, mdt = 9999997, min_i;
  8.  
  9.     while(true)
  10.     {
  11.         middle =  int(ceil((L+R)/2));
  12.  
  13.         if(middle == 0 || middle == c.size()-1)
  14.             return middle;
  15.  
  16.         if(val > c[middle])
  17.             L = middle;
  18.  
  19.         if(val < c[middle])
  20.             R = middle;
  21.  
  22.         if(val == c[middle])
  23.             return middle;
  24.  
  25.         dt = abs(val - c[middle]);
  26.  
  27.         if(dt < mdt){
  28.             mdt = dt;
  29.             min_i = middle;
  30.         }else if(dt == mdt){
  31.             return middle;
  32.         }else if(dt > mdt){
  33.             return min_i;
  34.         }
  35.     }
  36.  
  37.     return middle;
  38. }
  39.  
  40. int main()
  41. {
  42.     int N,M;
  43.     scanf("%d",&N);
  44.  
  45.     vector<int> Shirts(N);
  46.  
  47.     for(int i = 0; i < N; i++)
  48.         scanf("%d", &Shirts[i]);
  49.  
  50.     scanf("%d",&M);
  51.  
  52.     vector<int> TShirts(M);
  53.  
  54.     for(int i = 0; i < M; i++)
  55.         scanf("%d", &TShirts[i]);
  56.  
  57.     int Ms = -1, Mt = -1, Delta = 9999999;
  58.     for(int x = 0; x < N; x++)
  59.     {
  60.         int Nearest = bf(TShirts, Shirts[x]);
  61.  
  62.         int Dt = abs(TShirts[Nearest] - Shirts[x]);
  63.         if(Dt < Delta){
  64.             Delta = Dt;
  65.             Ms = x;
  66.             Mt = Nearest;
  67.  
  68.             if(Delta == 0){
  69.                 printf("%d %d", Shirts[Ms], TShirts[Mt]);
  70.                 return 0;
  71.             }
  72.         }
  73.     }
  74.  
  75.     printf("%d %d", Shirts[Ms], TShirts[Mt]);
  76.  
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement