I have a program which works but it is a bit too slow with big numbers.
nbBlocs
contains the size of the array, it can be up to 20000 and I enter the value inside on each position.
nbQ
is the number of queries (at most 20000 queries). For each query, it looks inside the array and tells me which is the closest value to it (by absolute difference). So, if my array is [0,2,5,11,24,32]
and the query is 10, it returns 11 because absolute difference (10-11) is the smallest.
Input example
7 (size of array)
41 32 11 17 24 8 16 (all the values inside array)
4 (nbQ)
9 20 28 11 (four queries)
Output
8 17 24 11
Here is my code :
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int nbBlocs;
cin >> nbBlocs;
int dens;
std::vector<int> tab(nbBlocs);
for(int i=0; i<nbBlocs; i++){
cin >> dens;
tab[i]=dens;
}
sort(tab.begin(), tab.end());
int nbQ;
cin >> nbQ;
int quest;
for(int j = 0; j<nbQ; j++){
cin >> quest;
int valSup=-1;
int valInf=-1;
int reponse=-1;
for(unsigned int i=0;i<tab.size();i++){
if(quest < tab[i]){
valSup = tab[i];
if(i!=0)
valInf = tab[i-1];
else
valInf = valSup;
}
if(i==(tab.size()-1) && valSup == -1){
valSup = tab[tab.size()-1];
valInf = valSup;
}
if(valSup != -1 && valInf != -1){
if(std::abs(quest - valSup) < (std::abs(quest - valInf))){
reponse = valSup;
break;
}
else if (std::abs(quest - valSup) == (std::abs(quest - valInf))){
reponse = valInf;
break;
}
else{
reponse = valInf;
break;
}
}
}
if (reponse != -1)
cout << reponse << endl;
}
}