這篇主要是記錄一些練習排序 的題目
Insertion Sort
這題的話，因為每塞入一個數就要求中位數，也就是每塞入一個數就要重新排序並算出中位數。這時候insertion sort就會是最好的方法，因為如果用quick sort、merge sort這些公認比較快的方法，每次整理的時間複雜度為O(nlogn)，而insertion sort只需要O(n)，相比之下快了很多，而且也比較容易實作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<stdio.h>
int main(){
int n,cnt=0,num[10000]={0},i;
while(scanf("%d",&n) != EOF){
for(i=cnt-1;num[i]>n;i--){
num[i+1] = num[i];
}
num[i+1] = n;
cnt++;
if(cnt%2){
printf("%d\n",num[cnt/2]);
}
else{
printf("%d\n",(num[cnt/2-1]+num[cnt/2])/2);
}
}
return 0;
}
|
Counting Sort
哪個點能滿足從他的家到所有的親戚的家的距離的和為最小 ？位於中位數的點就是這個萬中選一的角色。所以我們只要能找到中位數，然後累加每個點到中位數的距離 ，就能解決這題。
解題想法：
1.先看r是奇還是偶，奇的話只會有一個中位數，偶的話會有兩個。
2.若為奇，先找到所有門牌號碼的中位數，然後累加每個點與它的距離。
3.累加的策略：
跑一個0~30000的迴圈，每次直接相加所有i號到中位數門牌的距離。
距離 += | (中位數 - i) * (門牌為i的房子數量) |
因為(中位數-i)可能為負，所以用絕對值。
4.若為偶，就先用第2步、第3步的方法算出較小中位數的距離，並判斷較大中位數是否和較小中位數相等。
這邊的較大較小中位數指的是順位，假設有8個從小到大排好的門牌號碼，那第4個就是較小中位數，第5個就是較大中位數。
5.如果較大較小相等，直接輸出第4步算出來的結果。
6.如果較大較小不相同，則用第2步、第3步的方法算出較大中位數的距離，再來比較兩個中位數算出來的距離，並輸出距離較小的那個。
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
| #include<stdio.h>
#include<stdlib.h>
int main(){
int t,r,i,x;
scanf("%d",&t);
while(t--){
int s[30001]={0},cnt=0,loc,lod;
scanf("%d",&r);
for(i=0;i<r;i++){
scanf("%d",&x);
s[x]++;
}
long long d=0;
if(r%2){
for(i=0;i<30001;i++){
cnt += s[i];
if(cnt >= r/2+1){
loc = i;
break;
}
}
for(i=0;i<30001;i++){
if(s[i]){
d += abs((loc-i)*s[i]);
}
}
printf("%lld %d\n",d,loc);
}
else{
long long dd=0;
for(i=0;i<30001;i++){
cnt += s[i];
if(cnt >= r/2){
loc = i;
break;
}
}
for(i=0;i<30001;i++){
if(s[i]){
d += abs((loc-i)*s[i]);
}
}
for(i=0;i<30001;i++){
cnt += s[i];
if(cnt >= r/2+1){
lod = i;
break;
}
}
if(loc != lod){
for(i=0;i<30001;i++){
if(s[i]){
dd += abs((lod-i)*s[i]);
}
}
if(d <= dd){printf("%lld %d\n",d,loc);}
else{printf("%lld %d\n",dd,lod);}
}
else{
printf("%lld %d\n",d,loc);
}
}
}
return 0;
}
|
本來想說用LCS做，但我突然想到我只要統計這兩個字串的每個字母出現多少次，然後再照順序輸出就好，這樣的做法和counting sort很像，所以把這題歸在這邊。
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
| #include<stdio.h>
#include<string.h>
#define min(a,b) a<b?a:b
int main(){
char a[1001],b[1001];
while(scanf("%s%s",a,b) != EOF){
int acnt[26]={0}, bcnt[26]={0},i,j;
int al=strlen(a),bl=strlen(b),t;
for(i=0;i<al;i++){
acnt[a[i]-97]++;
}
for(i=0;i<bl;i++){
bcnt[b[i]-97]++;
}
for(i=0;i<26;i++){
t = min(acnt[i], bcnt[i]);
for(j=0 ; j<t ; j++){
printf("%c",i+97);
}
}
printf("\n");
}
return 0;
}
|
Others
這題很明顯的就是告訴我們一堆排序的規則，排序完就印出來，然後要注意輸入的ab可能為負，如果用C、C++，取得的餘數也會因此為負，所以我會先變成絕對值，這樣比較好處理。
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
| #include<bits/stdc++.h>
using namespace std;
int num[10005],n,m;
bool cmp(int a, int b){
int am = abs(a%2),bm = abs(b%2);
if(a%m != b%m){return a%m < b%m;}
if(am != bm){return a%2;}
if(am && bm){return a > b;}
return a < b;
}
int main(){
int i;
while(cin>>n>>m && n+m){
for(i=0;i<n;i++){cin>>num[i];}
sort(num, num+n, cmp);
cout<<n<<" "<<m<<"\n";
for(i=0;i<n;i++){
cout<<num[i]<<"\n";
}
}
cout<<"0 0\n";
return 0;
}
|
在討論區裡，可以看到有些人是先計次數，再排序，而我的作法是只算前面有幾個比自己大，然後把所有的結果相加印出，省下了排序的步驟。以下將證明我的想法可行：
我們令一陣列裡有{3,4,1,5,2}這五個數，且用sum表示交換次數。
圖一：討論區普遍的做法
圖二：我的做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<stdio.h>
int main(){
int n,i,j,num[1001];
while(scanf("%d",&n)!=EOF){
int chg=0;
for(i=0;i<n;i++){scanf("%d",&num[i]);}
for(i=1;i<n;i++){
for(j=i-1;j>=0;j--){
if(num[j] > num[i]){chg++;}
}
}
printf("Minimum exchange operations : %d\n",chg);
}
return 0;
}
|
程式碼有點複雜，我真的想不到怎麼精簡…
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
| #include<bits/stdc++.h>
#define speedup ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
struct sChar{
int ascii,cnt;
};
bool cmp(sChar a, sChar b){
if(a.cnt == b.cnt){
return a.ascii > b.ascii;
}
return a.cnt < b.cnt;
}
int main(){
speedup;
string s;
int first=0;
while(getline(cin, s)){
if(first){cout<<"\n";}
int asc[129]={0},i,j,sl=s.length();
for(i=0;i<sl;i++){
asc[s[i]]++;
}
int idx=0;
sChar chr[129];
for(i=0;i<129;i++){
if(asc[i]){
chr[idx].ascii = i;
chr[idx].cnt = asc[i];
idx++;
}
}
sort(chr,chr+idx,cmp);
for(i=0;i<idx;i++){
cout<<chr[i].ascii<<" "<<chr[i].cnt<<"\n";
}
if(!first){first = 1;}
}
return 0;
}
|
封面圖源：Pixiv
