Solution Idea

50063. Friend Distance

Solution

解題主要方向為從每一格位置將目前未放置的人放置一遍,計算目前最遠距離。

Note

  1. 因答案需輸出一組按字典序最小的解,故在輪流放置的時候以 A~Z 的順序測試,在相同距離答案下最先找到的順序解即為答案。
  2. 每格位置 $x_{th}$ 放置人時,只需計算他與前面 1~$(x-1)_{th}$ 的距離並記錄,不需全部重算,以防 TLE。
  3. 設一變數記錄目前最佳解的距離長度,如果目前計算的距離長度超過最佳解,即 cut。
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 <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
char A[16][16] = {0};
int N, M;
int bound = INT_MAX;
int isUse[16] = {0};
int ordering[16] = {0};
int ans[16] = {0};
 
void Ordering(int index, int dist){
    if(index > N){
        if(dist < bound){
            bound = dist;
            for(int i=1; i<=N; i++) ans[i] = ordering[i];
        }
        return;
    }
    if(dist >= bound) return;
 
    for(int i=0; i<N; i++){
        if(isUse[i]) continue;
        int tmpDist = dist;
        for(int j=1; j<index; j++){
            if(A[ordering[j]][i])
                if(index - j > tmpDist) tmpDist = index - j;
        }
 
        isUse[i] = index;
        ordering[index] = i;
        Ordering(index+1, tmpDist);
        isUse[i] = 0;
    }
    return;
}
 
int main(){
    scanf("%d %d", &N, &M);
    for(int i=0; i<M; i++){
        char x[2], y[2];
        scanf("%s %s", x, y);
        int a = x[0]-'A', b = y[0]-'A';
        A[a][b] = A[b][a] = 1;
    }
    Ordering(1, 0);
    printf("%d\n", bound);
    for(int i=1; i<=N; i++) printf("%c%c", ans[i]+'A', (i!=N)? ' ': '\n');
    return 0;
}

Advanced

  1. 預測放置一人後,最長距離至少會變成多少即可提前 cut ,減少執行時間。
  2. Binary Search

Discussion