iT邦幫忙

2021 iThome 鐵人賽

DAY 19
0
自我挑戰組

用 C & C++ 帶你手把手解 UVa 一顆星選集系列 第 19

Day 0x13 UVa299 Train Swapping

題意

  • 輸入火車的排列狀態,輸出需要交換多少次以排好順序
  • 需要注意的有:
    1. 輸入第一行一個整數 N 代表測資數
    2. 每筆測資第一行 L 代表火車長度 (0 ≤ L ≤ 50)
    3. 每次交換只能對調相鄰兩車廂
    4. 輸出格式
      • Optimal train swapping takes S swaps.

解法

  • 輸入測資數 N 並用 while 迴圈重複,再讀每筆測資長度 L 並存入整數陣列中
    int N;
    int L;
    int train[50] = {0};
    
    scanf("%d", &N);        //number of case
    
    while(N--){
    
        scanf("%d", &L);    //length of train
    
        for(i = 0; i < L; i++){
            scanf("%d", &train[i]);
        }
        ...
    }
    
  • 因為 L 的範圍很小,所以用泡沫排序的概念計算交換次數即可 (一星題嘛 XD)
    int count = 0;
    
    for(i = 0; i < L - 1; i++){
        for(j = 0; j < L - 1 - i; j++){
            if(train[j] > train[j + 1]){
                temp = train[j];
                train[j] = train[j + 1];
                train[j + 1] = temp;
                count++;
            }
        }
    }
    
    printf("Optimal train swapping takes %d swaps.\n", count);
    
  • C code
    #include<stdio.h>
    
    int main(){
    
        int N;
        int L;
        int train[50] = {0};
        int i, j;
        int temp;
    
        scanf("%d", &N);        //number of case
    
        while(N--){
    
            scanf("%d", &L);    //length of train
    
            int count = 0;
    
            for(i = 0; i < L; i++){
                scanf("%d", &train[i]);
            }
    
            for(i = 0; i < L - 1; i++){
                for(j = 0; j < L - 1 - i; j++){
                    if(train[j] > train[j + 1]){
                        temp = train[j];
                        train[j] = train[j + 1];
                        train[j + 1] = temp;
                        count++;
                    }
                }
            }
    
            printf("Optimal train swapping takes %d swaps.\n", count);
    
        }
    
        return 0;
    }
    

上一篇
Day 0x12 UVa10038 Jolly Jumpers
下一篇
Day 0x14 UVa10035 Primary Arithmetic
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言