UVa11242 - Tour de France(水題)

題目大意：

一個競速腳踏車由兩個齒輪與一條鏈子組成，鏈子則透過許多鏈輪組成，給你一些齒輪，並告訴妳這些齒輪的輪齒有多少，請幫忙選出兩個齒輪 (n/m)，n 是後輪、m 是前輪，定義為速率 \(d\)，要你找出兩個最大速率相除最大的數字。

最大速率有一些特別規定，如果有三種速度分別為 \(d_1, d_2 , d_3\)，排序為 \(d_1 < d_2 < d_3\)，那我們就不能拿 \(d_1 , d_2\) 來算最大速率，只能拿 \(d_1 \ and \ d_2 \) or \(d_2 \ and \ d_3 \) 進行相除。

題目連結

重點觀念

• 學會理解英文會話題目
• 能看出此題如何運作

分析：

其實這題不難，我們只要將全部的組合都嘗試一遍進行排序，找出相鄰的速率相除後的數字最大輸出即可。

需要注意的是 c++ sort 是由小到大，這點要特別注意。

參考來源

11242 – Tour de France - GSOURCECODE

心得

…，這題我寫了兩小時，完全思考錯 debug 方向，還以為是 cin 小數點的問題，一直在往這邊嘗試，直到找到了參考來源，互相比較後發現原來是我的 sort 排序完後，我自己會漏掉最後的一個數字去比較速率，現在改回來後，就好了很多，一次就 AC 啦！

題外話，往正確的 debug 方向走真的好難…，錯了都不知道。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
//#include <algorithm>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 20000
using namespace std;
int F,R;
double f[MAXN], r[MAXN], num[MAXN]; // f 前輪 r 後輪 num 速率

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> F >> R && F){
        for(int i = 0; i < F; i++) cin >> f[i]; //輸入資料
        for(int i = 0; i < R; i++) cin >> r[i]; //輸入資料

        int cnt = 0; //速率的最大長度
        for(int i = 0; i < R; i++){
            for(int j = 0; j < F; j++){
                num[cnt++] = r[i] / f[j]; //不斷交疊產生速率
            }
        }
        sort(num, num + cnt); //排序
        //for(int i = 0; i < cnt; i++ ) cout << num[i] << ' ';
        //cout << '\n';
        double d, dmax = 1; //dmax 是 1 是因為兩個數字一樣相比較最小會是 1，不會低於 1。
        for(int i = 1; i < cnt; i++){ //開始進行比較，找出兩個速率相差最大
            if(num[i] / num[i-1] >= dmax){ //如果 dmax 比較小
                dmax = num[i] / num[i-1]; //替換成這兩個速率相差
                //cout << "num is " << num[i] << ' ' << num[i+1] << '\n';
            }
        }
        cout << fixed << setprecision(2) << dmax << '\n'; 
        //輸出，題目要求小數點兩位，因此c++要這樣寫
    }
    return 0;
}