Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Created by Federico Bento & Ricardo Azevedo */
- #include <stdio.h>
- #include <stdlib.h>
- #define MAX 1000000
- void merge(int v[], int start, int middle, int end) {
- int i, p1, p2, aux[MAX];
- p1=start; // "Apontador" do array da metade esquerda
- p2=middle+1; // "Apontador" do array da metade direita
- i = start; // "Apontador" do array aux[] a conter juncao
- while (p1<=middle && p2<=end) { // Enquanto de para comparar
- if (v[p1] <= v[p2]) aux[i++] = v[p1++]; // Escolher o menor e adicionar
- else aux[i++] = v[p2++];
- }
- while (p1<=middle) aux[i++] = v[p1++]; // Adicionar o que resta
- while (p2<=end) aux[i++] = v[p2++];
- for (i=start; i<=end; i++) v[i] = aux[i]; // Copiar array aux[] para v[]
- }
- void mergesort(int v[], int start, int end) {
- int middle;
- if (start<end) { // Parar quando tamanho do array < 2
- middle = (start+end)/2; // Calcular ponto medio
- mergesort(v, start, middle); // Ordenar metade esquerda
- mergesort(v, middle+1, end); // Ordenar metade direita
- merge(v, start, middle, end); // Combinar duas metades ordenadas
- }
- }
- void binsearch(int v[], int start, int end, int key)
- {
- if(key > v[end]) {
- printf("%d\n", v[end]);
- return;
- }
- if(key < v[start]) {
- printf("%d\n", v[start]);
- return;
- }
- int middle;
- while(start < end) {
- middle = start + (end-start)/2;
- if(key < v[middle])
- end = middle;
- else
- start = middle + 1;
- }
- if(start == 0) printf("%d\n", v[start]);
- else if(v[start] == key) printf("%d\n", key);
- else if(v[start-1] == key) printf("%d\n", key);
- else if(abs(v[start]-key) == abs(v[start-1]-key)) printf("%d %d\n", v[start-1], v[start]);
- else if(abs(v[start]-key) < abs(v[start-1]-key)) printf("%d\n", v[start]);
- else printf("%d\n", v[start-1]);
- }
- int main()
- {
- int i, j, n, k = 0;
- scanf("%d", &n);
- int array[n];
- int sum[MAX];
- for(i = 0; i < n; i++)
- scanf("%d", &array[i]);
- for(i = 0; i < n; i++) {
- for(j = i+1; j < n; j++) {
- sum[k] = array[i] + array[j];
- k++;
- }
- }
- mergesort(sum, 0, k-1);
- scanf("%d", &n);
- int key[n];
- for(i = 0; i < n; i++)
- scanf("%d", &(*(i+key)));
- for(i = 0; i < n; i++)
- binsearch(sum, 0, k-1, key[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement