Solução por Sofhia Souza
Para resolver esse problema, é necessário conhecimento sobre o algoritmo de busca binária.
Se fossemos testar todos os possíveis pares de casas, o algoritmo ficaria quadrático, o que é muito lento para 
. Logo, teremos que, para cada casa 
, fazer uma busca binária no vetor de casas para encontrar a casa y, onde 
é igual (ou o mais próximo) de 
. Assim que encontrarmos uma soma igual a , imprimimos os dois valores.
Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| #define MAXN 100010 | |
| using namespace std; | |
| int main() | |
| { | |
| int n, vet[MAXN], k; | |
| cin >> n; | |
| for(int i = 0 ; i < n ; i++) | |
| { | |
| cin >> vet[i]; | |
| } | |
| cin >> k; | |
| for(int i = 0 ; i < n ; i++) //faço a busca binária para cada casa | |
| { | |
| int ini = 0, fim = n-1, r; | |
| while(ini <= fim) | |
| { | |
| int meio = (ini+fim)/2; | |
| if(vet[i] + vet[meio] >= k) | |
| { | |
| r = meio; | |
| fim = meio-1; | |
| } | |
| else ini = meio+1; | |
| } | |
| if(vet[i] + vet[r] == k) //se encontrei uma soma que é igual a k, printo os dois valores | |
| { //primeiro o menor e depois o maior, e dou um break | |
| cout << min(vet[i], vet[r]) << ' ' << max(vet[i], vet[r]) << "\n"; | |
| break; | |
| } | |
| } | |
| } |