作業六題解
===
本週的主題是Greedy Algorithm，以下是[俄羅斯娃娃](https://judge.ccns.io/problems/17)與[青娃過河](https://judge.ccns.io/problems/18)的題解。
## [俄羅斯娃娃](https://judge.ccns.io/problems/17)
- Task Provider: UVA 11100
- Task Setter: MinHsuan

### 解法說明
這題出的不太好，因過度簡化題目導致不需要使用Greedy也很輕易就能得到答案，先跟大家道個歉。題目上應該增加一個條件，**請盡可能將每個娃娃的層數是最少的**，以下就已加入條件後的題目做講解。

這題的想法非常簡單，可以分為兩個關鍵部分
1. 得到娃娃的集合數量(即有幾組娃娃)
- 每組俄羅斯娃娃的大小會符合 X~i-1~ < X~i~ < X~i+1~，因此出現最多次的數字，至少會有他出現次數的組數。
2. 平均分配娃娃讓每組娃娃層數盡可能少
- 代表要讓集合內元素盡量都是最少的，因此我們可以平均分配給娃娃到集合內。

有了上述的想法，先設定總共有 $m$ 個數字，首先將陣列排序，接著找到出現次數最多的數字，假定他的次數是 $n$ ，間隔 $n$ 個數字取出數字放入集合，完成第一個集合，依序執行 ${m \over n}$ 次後，即可得到所有集合內的內容。

有些人可能會覺得困惑，這樣會不會有同個集合內有兩個一樣的數字呢？
不用擔心，因為一個數字最多出現 n 次，因此間隔 n 個數字即可避免取到同一個數字。

### 參考解答
提供一個簡單的解答，直接排序後，計算出現最多次的數字，並且輸出即可。

本解答適用於新增條件後的題目，也適用於原題。

:::spoiler

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
int d[1001], N, n;
unordered_map <int, int> m;    //存放數字出現次數
int main(){
    cin >> N;
    n = N;
    while(N--)
        cin>> d[N];
    for(auto i=0;i<n;i++){    //統計數字出現次數
        if(m.find(d[i])==m.end())
            m[d[i]] = 1;
        else m[d[i]]++;
    }
    int interval = 0;
    for(auto i=m.begin();i!=m.end();i++)    //找出最大的出現次數
        interval = max(interval, i->second);
    sort(d, d + n);    //排序陣列
    for(auto i=0;i<interval;i++){    //依據間隔輸出答案
        for(auto j=i;j<n;j+=interval)
            cout << d[j] << " ";
        cout << endl;
    }
    return 0;   
}

:::

## [青蛙過河](https://judge.ccns.io/problems/18)
- Task Provider: UVA 11157
- Task Setter: MinHsuan
### 解法說明
題目提到可能有大石頭與小石頭，大石頭可以無限次使用，小石頭只能夠使用一次。大石頭的部分很簡單，只要下一塊最近的石頭是大石頭，不需要考慮直接選擇就行，小石頭的部分則需要考慮石頭使用的分配，假設某塊石頭去程先用掉，回程則無法使用，某些狀況下回程會需要這塊石頭來達成最小距離。
我們可以想想，回程其實也只是一些石頭位置的分配，分配好這些石頭後，不管向前跳向後跳都是一樣的，因此可以將題目轉換成兩隻青蛙往目的地跳，途中這兩隻青蛙共同計算每次跳的距離（說是兩隻青蛙，但都是小青本蛙）。這題Greedy的想法便是在這裡，每次遇見小石頭時，我們讓離石頭比較遠的青蛙跳過來（選近的青蛙的話，比較遠的青蛙下次又變得更遠了），這樣子兩隻青蛙輪流使用近的石頭，就不會有其中一隻越來越遠了，重複這樣的行為，便可以得到答案。

### 參考解答
:::spoiler

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
deque<int> b, s;
int T, N, P;
int ans, pos_go, pos_back, r_size;
char rock;

int main(){
    cin >> T;
    while (T--){
        cin >> N >> P;
        b.clear();
        s.clear();
        for(int i=0;i<N;i++){
            cin >> rock >> r_size;
            if(rock == 'b')
                b.push_back(r_size);
            else if(rock == 's')
                s.push_back(r_size);
        }
        ans = 0;    //每次青蛙跳躍的時候，紀錄最遠的跳躍距離
        pos_go = 0;    //pos_go, pos_back紀錄目前青蛙的位置
        pos_back = 0;
        for(int i=0;i<N;i++){
            if(s.empty() || !b.empty() && b.front() < s.front()){   //下一顆最近的是大石頭，一起跳上去
                ans = max(ans, b.front()-pos_go);
                pos_go = b.front();
                ans = max(ans, b.front()-pos_back);
                pos_back = b.front();
                b.pop_front();
            }
            else{   //下一顆最近的是小石頭
                if(pos_go < pos_back){    //看誰比較遠，遠的跳上去
                    ans = max(ans, s.front()-pos_go);
                    pos_go = s.front();
                }
                else{
                    ans = max(ans, s.front()-pos_back);
                    pos_back = s.front();
                }
                s.pop_front();
            }
        }
        ans = max(ans, P-pos_go);
        ans = max(ans, P-pos_back);
        cout << ans <<endl;
    }
}

:::