50031. Pairing
難度：3.8/51
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct num{
int val;
int idx;
} num;
typedef struct pair{
struct num* a;
struct num* b;
int sum;
} pair;
int cmp_num(const void *a, const void *b){
num* num_a = (num*)a;
num* num_b = (num*)b;
return num_a->val - num_b->val;
}
void swap_num(num** a, num** b){
num **t = a;
a = b;
b = t;
}
int cmp_inc(const void *a, const void *b){
pair* pair_a = (pair*)a;
pair* pair_b = (pair*)b;
if(pair_a->sum > pair_b->sum) return 1;
else if(pair_b->sum > pair_a->sum) return -1;
else return pair_a->a->idx - pair_b->a->idx;
}
int cmp_dec(const void *a, const void *b){
pair* pair_a = (pair*)a;
pair* pair_b = (pair*)b;
if(pair_a->sum > pair_b->sum) return -1;
else if(pair_b->sum > pair_a->sum) return 1;
else return pair_b->b->idx - pair_a->b->idx;
}
void print_pair(pair* p, int reverse){
if(!reverse) printf("%d = numbers[%d] + numbers[%d]\n", p->sum, p->a->idx, p->b->idx);
else printf("%d = numbers[%d] + numbers[%d]\n", p->sum, p->b->idx, p->a->idx);
}
void pairPrint(int numbers[], int n){
num* num_arr = (num*) malloc(sizeof(num) * n);
for(int i = 0; i < n; i++){
num_arr[i].val = numbers[i];
num_arr[i].idx = i;
}
qsort(num_arr, n, sizeof(num), cmp_num);
pair* pair_arr = (pair*) malloc(sizeof(pair) * (n / 2));
for(int i = 0; i < n / 2; i++){
pair_arr[i].a = &(num_arr[i]);
pair_arr[i].b = &(num_arr[n - i - 1]);
pair_arr[i].sum = (pair_arr[i].a)->val + (pair_arr[i].b)->val;
if((pair_arr[i].a)->idx > (pair_arr[i].b)->idx){
num* temp = pair_arr[i].a;
pair_arr[i].a = pair_arr[i].b;
pair_arr[i].b = temp;
}
}
#ifdef INC
qsort(pair_arr, n / 2, sizeof(pair), cmp_inc);
for(int i = 0; i < n / 2; i++) print_pair(&(pair_arr[i]), false);
#endif
#ifdef DEC
qsort(pair_arr, n / 2, sizeof(pair), cmp_dec);
for(int i = 0; i < n / 2; i++) print_pair(&(pair_arr[i]), true);
#endif
}