UVa 11389 The Bus Driver Problem

題意：
    有n個司機，早班有n條路線，晚班也有n條路線，這2n條路線都有不同的距離，要安排每一個司機早班和晚班各一條路線，但是如果早班+晚班的路線距離超過d的話，超過每1單位就要加班費r元，求如何安排路線給每位司機使得全部加班費為最小，並輸出。

想法：
    將早班n條路線由小到大排序，晚班也是，為了使得加班費總和最少，安排時就要盡量填滿d，因此早班最短配上晚班最長路線，然後早班第二短配上晚班第二長,.....依此類推。如果最短配上最短，會導致該路線和遠小於d，表示浪費了這位司機還剩下的距離，因此要盡量讓每位司機平均填滿d。

UVa 501 Black Box

想法：
    原本是用multiset來存每個數字，因為multiset為紅黑樹，想說從第一個元素iterate i次來GET第i個數字，但一個一個iterate效率太慢就TLE了。
    後來改用vector來存數字，每新增一個數字，就用binary search找到它該放的位置，然後用vector的insert來插入該數字，要GET第i個元素因為是vector就可以直接存取了，效率還不錯，UVa花了0.495秒。



這是用set的版本：

UVa 10763 Foreign Exchange

想法：
　　先對出發地排序一次，再對目的地排序一次，兩兩比較是否一樣即可。

UVa 10222 Decode the Mad man

想法：
　　先建立一個鍵盤keyboard，然後輸入一個字元c之後就找在keyboard裡的index，並輸出keyboard[i-2]。

UVa 579 ClockHands

想法：
　　題目很長但只是時針和分針夾角幾度，先將時針指的地方換成分鐘表示，然後時針分針相減後換成角度表示即可。

UVa 10905 Children's Game

想法：
　　對每個數字做排序，排序用STL_sort，cmp函數裡面就比較a和b兩個數字是(ab)比較大還是(ba)比較大決定排序方式，最後依序輸出即可。

UVa 401 Palindromes

本題連結
想法：
　　處理鏡像的部份我是把它存成陣列，Mir[]="AAE3HHIIJLLJ...."，比對兩個字元是否為鏡像，則看Mir[i]和Mir[i+1]是否符合，另外要注意本題每個輸出之間還要空一行。

UVa 445 Marvelous Mazes

題意：
　　遇到每個數字是"加起來"，如23X，則輸出5個X，2X12*，則輸出XX***，b表示空格，!則要換行。

UVa 414 Machined Surfaces

題意：
　　固定左右兩邊形狀，合併後會有多少個空格
想法：
　　計算每一列有多少個X，並找出哪一列有最多個X，值為Max，則該列空格就是(Max-該列有幾個X)

UVa 10082 WERTYU

想法：
　　用一個陣列代表鍵盤按鍵：char keyboard[]="QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"，然後找出輸入字元的i值，再輸出keyboard[i-1]。

UVa 10101 Bangla Numbers

想法：
　　透過遞迴求出答案。

UVa 642 Word Amalgamation

本題連結
想法：
　　給不同的單字不同的Hash值，在比對Hash值來找。


2014/2/23 更新： C++(11)寫法

UVa 11489 Integer Game

http://uva.onlinejudge.org/external/114/11489.html
題意：
　　由S先開始，每次拿掉一個數字都要使得剩下的"位數和"是3的倍數，如果找不到數字拿掉就輸了。

想法：
　　我們知道如果數字和為3的倍數，那麼接下來要拿掉的數字必須為3的倍數，才能繼續使得數字和為3的倍數。本題可將一連串的數字分成兩組：3的倍數和非3的倍數，然後有3種情況：

1. 如果非3倍數的數字和是3的倍數：那麼只要看3的倍數的數字個數是奇數個還偶數個就能決定贏家，因為當拿完3的倍數的數字後就無法再拿任何數字了。
2. 如果非3倍數的數字和不是3的倍數：
   那麼需要確認是否能從非3倍數的數字中找出使得數字和為3的倍數，
   ＊如果找的到，那麼就可以回到狀況1
   ＊如果找不到，代表是T獲勝，因為從一開始就無法拿掉任何數字。

UVa 10189 Minesweeper

題目連結

想法：
　　判斷如果輸入的字元為'*'，就將其八個方向都+1，最後輸出每個位置的數量。

註：本題只有Case與Case之間才有空行

UVa 10077 The Stern-Brocot Number System

題目連結

想法：
　　初始化三個數L=0/1, M=1/1, R=1/0，設輸入的分數為a：

• 如果a<M，那麼要往左邊走，
      R = M;
      M = (L分子+M分子)/(L分母+M分母);
• 如果a>M，往右邊走，
      L = M;
      M = (R分子+M分子)/(R分母+M分母);
• 如果a==M，停止。

這題和二分搜尋很類似。

UVa 10050 Hartals

本題題目連結

題意：
　　每個政黨都有發表演講的週期，只要星期日~星期四該天有任何一個政黨演講，hartal數目就+1，最後輸出hartal。
想法：
　　日數從1開始，每天對每個政黨的週期取餘數，若為0代表該日那個政黨有演講，hartal++。

UVa 834 Continued Fraction

本題題目連結

想法：
　　這題可以自己舉幾個例子算出分數，找出規則，解法如下，由題目Example，從(43,19)逆推回去

1. 首先2的話就是43/19=2,43%19=5，那麼現在[2;] & (5,19)
2. 19/5=3,19%5=4，得到[2;3] & (5,4)
3. 倒數的緣故，交換兩數，現在[2;3] & (4,5)
4. 重複2~3步驟，直到第一個數為1

UVa 846 Steps

題意：
　　給定兩地的位置x,y，其距離為(x-y)，而第一步和最後一步的距離皆規定為1，每次踏下一步的距離只能比上一步的距離多1或少1或一樣，本題求最少走的步數，從Example來看x=45,y=50，距離為5，其最少步數為{1,2,2,1}。

想法：
　　因為本題只要求最少的步數即可，因此過程如何安排就不重要，只要符合規定即可，所以我們可以先一步從起點一步從終點開始往中間走，變成{1,1},{1,2,2,1},{1,2,3,3,2,1}...這樣，舉個例子如果兩地距離為14，那麼剛才的算法到{1,2,3,3,2,1}就會停止，因為已經12了，在+2*4就會超過14，這時候只要判斷12+4<14，再走一步就可以了，我們不管這步應該排在哪個位置，反正這步的距離一定<=4。還要考慮另外兩種情況，分別是兩地距離如果為17，那麼12+4<17，就要再兩步，而如果兩地距離為12，那麼就剛好。

UVa 10038 Jolly Jumpers

題意：
　　N個數的數列中，(1,2,3...,N-1)這些值都要被兩數字的差值涵蓋到，從Example來說，(1,4,2,3)的差值分別為(3,2,1)，所以有涵蓋(1~3)，因此為Jolly，(1,4,2,-1,6)的差值為(3,2,3,5)沒有涵蓋(1~5)所以不是Jolly

POJ 1664 放蘋果

想法：

　　因為盤子皆一樣，例如(1,1,3)和(1,3,1)是同樣的，所以排的時候以遞增的方式排，只保留(1,1,3)這組，故左邊的數字不大於右邊的數字。在一開始(0,0,0)時，若最左邊的盤子要+1，則右邊兩個也要跟著+1才能使上面的條件成立，照此規則，當某個盤子要+1時，其右邊的盤子也要跟著+1，所以要注意此動作是否會造成蘋果不夠(if(m-i>=0))，而當蘋果剛好分完(m=0)或是只剩最右邊的盤子(n=1)時，遞迴結束。