iT邦幫忙

2021 iThome 鐵人賽

DAY 18
0
自我挑戰組

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

Day 0x12 UVa10038 Jolly Jumpers

題意

  • 輸入一串數字,輸出是否為 Jolly Jumper
  • 需要注意的有:
    1. 每筆測資第一個整數代表有 n 個數字
    2. Jolly Jumper 定義
      • 數列中相鄰數字的差分別為 1~n-1 (順序沒差)
    3. 輸出格式
      • Jolly
      • Not jolly

解法

  • 重複讀入 n 後用 for 迴圈分別存入整數陣列裡
    int n;
    
    while(scanf("%d", &n) != EOF){
    
        int arr[3000] = {0};
    
        for(i = 0; i < n; i++){
            scanf("%d", &arr[i]);
        }
    }
    
  • 計算每兩數之間的差並存入陣列裡
    int S[3000] = {0};
    
    for(i = 0; i < n - 1; i++){
        S[i] = abs(arr[i] - arr[i + 1]);
    }
    
  • 對差值的陣列進行排序
    for(i = 0; i < n - 1; i++){
        for(j = i + 1; j < n - 1; j++){
            if(S[i] > S[j]){
                temp = S[i];
                S[i] = S[j];
                S[j] = temp;
            }
        }
    }
    
  • for 迴圈檢查是否 1~n-1 都有對應的差值;若有不同便跳出迴圈,根據 flag 的狀態輸出結果
    for(i = 0; i < n - 1; i++){
        if(S[i] != i + 1){
            flag = true;
            break;
        }
    }
    
    if(flag){
        printf("Not jolly\n");
    }
    else{
        printf("Jolly\n");
    }
    
  • C code
    #include<stdio.h>
    #include<stdbool.h>
    
    int main(){
    
        int n;
        int i, j;
        bool flag;
        int temp;
    
        while(scanf("%d", &n) != EOF){
    
            int arr[3000] = {0};
    
            for(i = 0; i < n; i++){
                scanf("%d", &arr[i]);
            }
    
            int S[3000] = {0};
    
            for(i = 0; i < n - 1; i++){
                S[i] = abs(arr[i] - arr[i + 1]);
            }
    
            for(i = 0; i < n - 1; i++){
                for(j = i + 1; j < n - 1; j++){
                    if(S[i] > S[j]){
                        temp = S[i];
                        S[i] = S[j];
                        S[j] = temp;
                    }
                }
            }
    
            flag = false;
    
            for(i = 0; i < n - 1; i++){
                if(S[i] != i + 1){
                    flag = true;
                    break;
                }
            }
    
            if(flag){
                printf("Not jolly\n");
            }
            else{
                printf("Jolly\n");
            }
        }
    
        return 0;
    }
    
  • C++
    • 可用 sort 加快速度;vectormap 等 STL 快速查找與動態儲存
    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
    
        int n;
        int i;
        bool flag;
        int temp;
    
        while(cin >> n){
    
            vector<int> v;
            vector<int> d;
    
            for(i = 0; i < n; i++){
                cin >> temp;
                v.emplace_back(temp);
            }
    
            for(i = 0; i < n - 1; i++){
                d.emplace_back(abs(v[i] - v[i + 1]));
            }
    
            sort(d.begin(), d.end());
    
            flag = false;
    
            for(i = 0; i < n - 1; i++){
                if(d[i] != i + 1){
                    flag = true;
                    break;
                }
            }
    
            if(flag){
                cout << "Not jolly\n";
            }
            else{
                cout << "Jolly\n";
            }
        }
    
        return 0;
    }
    

上一篇
Day 0x11 UVa100 The 3n + 1 problem
下一篇
Day 0x13 UVa299 Train Swapping
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言