[演算法題目] Tandem Bicycle

本題資訊

難度：easy
使用語言：C++
相關概念：Greedy Algorithm

題目敘述

You’re given two lists of positive integers: one that contains the speeds of riders wearing red shirts and one that contains the speeds of riders wearing blue shirts. Each rider is represented by a single positive integer, which is the speed that they pedal a tandem bicycle at. Both lists have the same length, meaning that there are as many red-shirt riders as there are blue-shirt riders. Your goal is to pair every rider wearing a red shirt with a rider wearing a blue shirt to operate a tandem bicycle.

Write a function that returns the maximum possible total speed or the minimum possible total speed of all of the tandem bicycles being ridden based on an input parameter, fastest. If fastest = true, your function should return the maximum possible total speed; otherwise it should return the minimum total speed.

“Total speed” is defined as the sum of the speeds of all the tandem bicycles being ridden. For example, if there are 4 riders (2 red-shirt riders and 2 blue-shirt riders) who have speeds of 1, 3, 4, 5, and if they’re paired on tandem bicycles as follows: [1, 4], [5, 3], then the
total speed of these tandem bicycles is 4 + 5 = 9.

Input:
redShirtSpeeds = [5, 5, 3, 9, 2]
blueShirtSpeeds = [3, 6, 7, 2, 1]
fastest = true

Output:
32

一樣是很冗長的題目。要先知道一個協力車原則：車子速度一定是以腳踩比較快的那個人為主，速度比較慢的那個人是廢咖。現在我們有了兩列人馬：紅隊和藍隊的個人速度，一台協力車必須是紅隊的人配上藍隊的人，寫出一個函式能回傳隊伍所能配出的最大速度或是最小速度。

Idea

看到 array 又要配對就很想排序。排序完後，如果是要找最快速度，我的想法是希望速度較快的，可以配上另外一隊速度較慢的，這樣才不會浪費掉速度較快的。例如紅隊最快速度是 9，藍隊最快速度是 7，我會希望他們不要在同一台協力車上。

所以排序後巡覽，以 redShirtSpeeds 來說從 index=0，也就是最小的速度開始，我會希望 blueShirtSpeeds 從最大那一個開始配對。而若 fastest 是 false 的話，那就用最浪費的配法，排序後依照排序順序一一配對就好，保證最浪費人才，達成速度最慢的目的XD

#include <vector>
using namespace std;

int tandemBicycle(vector<int> redShirtSpeeds, vector<int> blueShirtSpeeds, bool fastest) {
  sort(redShirtSpeeds.begin(), redShirtSpeeds.end());
  sort(blueShirtSpeeds.begin(), blueShirtSpeeds.end());
  int total = 0;

  for (int i = 0; i < redShirtSpeeds.size(); i++){
    if (fastest){
      int blueRider = blueShirtSpeeds[blueShirtSpeeds.size() - i - 1]; //因為太長，所以額外設了一個變數
      total += max(redShirtSpeeds[i], blueRider); //
    } else {
      total += max(redShirtSpeeds[i], blueShirtSpeeds[i]); //要找最慢，兩列都從頭巡覽
    }
  }
  return total;
}

時間複雜度：\(O(n\log n)\)，\(n\) 是協力車隊伍長度。
空間複雜度：\(O(1)\)