50052. K-means Algorithm
難度：4.5/5 Used Time: 39:561
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct vector{
int arr[16];
int group;
} vector;
int n, l, r;
vector v[64];
vector lead[3];
void print_v_num(vector* v){
for(int i = 0; i < l; i++) printf("%d ", v->arr[i]);
printf("\n");
}
void print_v_char(vector* v){
for(int i = 0; i < l; i++) printf("%c", v->arr[i]);
printf("\n");
}
void copy(vector* from, vector* to){
for(int i = 0; i < l; i++) to->arr[i] = from->arr[i];
}
int dist(vector* a, vector* b){
int ans = 0;
for(int i = 0; i < l; i++) ans += abs(a->arr[i] - b->arr[i]);
return ans;
}
int is_less(vector* a, vector* b){
for(int i = 0; i < l; i++){
if(a->arr[i] == b->arr[i]) continue;
else return a->arr[i] < b->arr[i];
}
return 0;
}
int cmp(const void* a, const void* b){
return !is_less((vector*)a, (vector*)b);
}
void ipt(){
scanf("%d %d %d", &n, &l, &r); getchar();
for(int i = 0; i < n; i++){
for(int j = 0; j < l; j++) v[i].arr[j] = getchar();
getchar();
}
for(int i = 0; i < 3; i++) copy(&v[i], &lead[i]);
}
void k_mean(){
for(int i = 0; i < n; i++){ vector* now_v = &v[i];
int min_dist = INT_MAX, min_idx = -1;
for(int j = 0; j < 3; j++){ vector* now_lead = &lead[j];
int now_dist = dist(now_v, now_lead);
if(now_dist < min_dist) min_dist = now_dist, min_idx = j;
else if(now_dist == min_dist && is_less(now_lead, &lead[min_idx])) min_idx = j;
}
now_v->group = min_idx;
}
vector avg[3];
for(int i = 0; i < 3; i++) for(int j = 0; j < l; j++) avg[i].arr[j] = 0;
for(int i = 0; i < 3; i++){ vector* now_avg = &avg[i];
int cnt = 0;
for(int j = 0; j < n; j++){ vector* now_v = &v[j];
if(now_v->group != i) continue;
for(int k = 0; k < l; k++){
now_avg->arr[k] += now_v->arr[k];
}
cnt += 1;
}
for(int k = 0; k < l; k++){
now_avg->arr[k] /= cnt;
}
}
for(int i = 0; i < 3; i++){ vector* now_avg = &avg[i];
int min_dist = INT_MAX, min_idx = -1;
for(int j = 0; j < n; j++){ vector* now_v = &v[j];
if(now_v->group != i) continue;
int now_dist = dist(now_avg, now_v);
if(now_dist < min_dist) min_dist = now_dist, min_idx = j;
else if(now_dist == min_dist && is_less(now_v, &v[min_idx])) min_idx = j;
}
copy(&v[min_idx], &lead[i]);
}
}
void opt(){
qsort(lead, 3, sizeof(vector), cmp);
for(int i = 0; i < 3; i++) print_v_char(&lead[i]);
}
int main(){
ipt();
while(r--) k_mean();
opt();
}