STEP5::Problem 0087 : 中♂位♂數

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0087
這題題目會讓你判斷一個亂序數列的中位數(你只知道第幾個但不知道數字),每次可以卻定A、B、C(任意三數)誰是這三數中的中位數。

做法是先固定一個AB,然後枚舉C,如果B是中位數把C塞到”右邊”陣列,如果C是中位數塞到中間,如果A是中位數塞到左邊。
做完後可以切成5段,左、A、中、B、右,看看數量就可以知道中位數在哪一段,如果不是A或B就用A或B重複執行上述步驟到那段只剩下1個數字,就得到中位數了。
要注意重複執行的時候A或B要固定,才能確保左邊、右邊不會塞反了(反了就悲劇…)
code很醜很想重寫……

1
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include "special_0087.h"
using namespace std;
//int W[10]={0,7,3,5,4,2,6,9,1,8};
int _mid(int[],int[],int[],int,int,int);
int Med3(int,int,int);
void chh(int[],int);
int n,M,le=0,ri=0,TT[1500];
int main(int argc,char *argv[])
{
srand(2);
int as,a,b,T1[1500],T2[1500],T3[1500],t1=0,t2=0,t3=0;
n=GetN();
//n=9;
M=(n+1)/2;
for(int i=0;i<n;i++)
T1[i]=i+1;
t1=n-2;
a=n-1;
b=n;
//printf("%d ",T1[n-1]);
as=_mid(T1,T2,T3,a,b,t1);
//Answer(as);
printf("%d\n",as);
system("pause");
return EXIT_SUCCESS;
}
int _mid(int T1[],int T2[],int T3[],int a,int b,int tt){
int l,t1=0,t2=0,t3=0;
for(int i=0;i<tt;i++)TT[i]=T1[i];
//for(int i=0;i<tt;i++)printf("%d ",TT[i]);
//puts("\n");
for(int i=0;i<tt;i++){
l=Med3(a,b,TT[i]);
if(l==a){
T3[t3++]=TT[i];
}else if(l==b){
T1[t1++]=TT[i];
}else if(l==TT[i]){
T2[t2++]=TT[i];
}
}
/*for(int i=0;i<t1;i++)printf("%d(%d) ",T1[i],W[T1[i]]);
puts(" T1\n");
for(int i=0;i<t2;i++)printf("%d(%d) ",T2[i],W[T2[i]]);
puts(" T2\n");
for(int i=0;i<t3;i++)printf("%d(%d) ",T3[i],W[T3[i]]);
puts(" T3\n");*/
//printf("1:%d 2:%d\n",le,ri);
if(le+t1+1==M){
//puts("L\n");
return b;
}else if(ri+t3+1==M){
//puts("R\n");
return a;
}else if(le+t1+1>M){
//puts("L-\n");
if(t1==1)return T1[0];
ri+=t2+t3+1;
chh(T1,t1);
return _mid(T1,T2,T3,b,T1[t1-1],t1-1);
}else if(ri+t3+1>M){
//puts("R+\n");
if(t3==1)return T3[0];
le+=t1+t2+1;
chh(T3,t3);
return _mid(T3,T1,T2,T3[t3-1],a,t3-1);
}else{
//puts("LR\n");
if(t2==1)return T2[0];
le=le+t1;
ri=ri+t3+1;
chh(T2,t2);
return _mid(T2,T1,T3,T2[t2-1],b,t2-1);
}
}
void chh(int TT[],int tt)
{
int pi=rand()%(tt-1),tmp=TT[pi];
TT[pi]=TT[tt-1];TT[tt-1]=tmp;
return;
}
/*
int Med3(int A,int B,int C){
int a=W[A];
int b=W[B];
int c=W[C];
//printf("A:%d B:%d C:%d\n",a,b,c);
if(a>b&&a<c)return A;
if(a<b&&a>c)return A;
if(a>b&&b>c)return B;
if(a<b&&b<c)return B;
if(a>c&&b<c)return C;
if(a<c&&b>c)return C;
}
*/
/*
int GetN()¡G¤@¶}©l´N©I¥s¡A¥B¤£§t¥ô¦ó°Ñ¼Æ¡F¦^¶ÇNªº­È¡C
2.int Med3(int x,int y,int z)¡G©I¥s®É»Ýµ¹3­Ó¤£¦P¤Hªº¥N¸¹·í°Ñ¼Æ¡F¦^¶Ç³o3­Ó¤H¤¤¹ê¤O©~©ó¤¤¶¡ªº¤H¥N¸¹¡C
3.void Answer(int ans)*/