作業四題解
===
###### tags: `成大演算法春季課程`

## [Maximum Gap](https://judge.ccns.io/problems/11)
- Task Provider: 參考 [Leetcode : 164. Maximum Gap](https://leetcode.com/problems/maximum-gap/)
- Task Setter: joey3639570

### 解法說明
這題雖然在 Leetcode 上面標註是 Hard ，但其實概念很簡單，就是看兩數之間的差距並且記錄下來，但在這裡我們針對時間有些限制，其中幾個測資較多的狀況會碰到 TLE ，於此其實希望的是你的程式能以 linear time and uses linear extra space 執行，於此，我們使用 **Bucket Sort** 的概念來解決這個問題。
(但助教這裡 Time limit 設置的沒有很好，如果有單項 TLE 的問題，多交幾次應該會過)

### 參考解答

#include <iostream>
#include <cmath>
#include <vector>
#include <climits>

using namespace std;

int maximumGap(vector<int>& nums) {
        if(nums.size()<2) return 0;
        
        int maxi = -1, mini = INT_MAX, n = nums.size();
        for(auto u : nums) maxi = max(maxi,u), mini = min(mini,u);
		int avg_gap = (int)ceil((double)(maxi-mini)/(n-1));
        // To handle cases where all the elements are same!!!
        if(avg_gap == 0) return 0;
		vector <int> bucket_max(n,-1), bucket_min(n,INT_MAX);
        for(int i = 0; i<n; i++){
            int index = (nums[i]-mini)/avg_gap;
            bucket_min[index] = min(bucket_min[index],nums[i]);
            bucket_max[index] = max(bucket_max[index],nums[i]);
        }
        
        // After filling the min and max arrays, we just need to compare...
        int prev = mini, ans = 0;
        for(int i = 0; i<bucket_min.size(); i++){
            if(bucket_max[i] == -1) continue;
            ans = max(ans,bucket_min[i]-prev);
            prev = bucket_max[i];
        }
        // We need to compare with the last element which is maximum...
        ans = max(ans,maxi-prev);
        return ans;
}
	
int main () {
    int a, n;
    vector<int> inputs;
    std::cin >> n;
    while (n--) {
        std::cin >> a;
        inputs.push_back(a);
    }
    
	int result = maximumGap(inputs);
	cout << result;
	
    return 0;
}

## [Sort Characters By Frequency](https://judge.ccns.io/problems/12)
- Task Provider: 參考 [Leetcode : 451. Sort Characters By Frequency](https://leetcode.com/problems/sort-characters-by-frequency/)
- Task Setter: joey3639570

### 解法說明
此題是想讓各位應用 Sort ，排序不僅僅只會有比數值本身大小的狀況，也有可能出現在像此題所說的 Frequency ，且本身額外納入了 ASCII Code 的順序問題，在此題我使用 `unordered_map` 搭配更動 `std::sort` 的比較條件及結果來製造出 Frequency Sort。

### 參考解答
在 `compare` 裡所設置的 `operator()`，目的是除了 frequency 大小依據外，額外設置當 frequency 相同時，以該字母 ASCII Code 大小為依據做比較。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <unordered_map>
#define MAXN 500000

using namespace std;

class compare
{
   public:
   bool operator()(pair<char,int>&p1,pair<char,int>&p2)
   {
           return p1.second != p2.second?  p1.second > p2.second : p1.first < p2.first;
   }

};

string frequencySort(string s) {
   int n=s.length();
   unordered_map<char,int>map;
   for(int i=0;i<n;i++)
   {
	   map[s[i]]++;
   }
   vector<pair<char,int>>sorted(map.begin(),map.end());
   sort(sorted.begin(),sorted.end(),compare());
   string ans;
   for(int i=0;i<sorted.size();i++)
   {
	   for(int j=0;j<sorted[i].second;j++)
	   {
		   ans+=sorted[i].first;
	   }
   }
   return ans;
}

int main () {

	string inputs;
	
	cin >> inputs;
	inputs = frequencySort(inputs);	
	cout << inputs;

    return 0;
}

## [調酒挑選](https://judge.ccns.io/problems/13)

* Task Provider: visitorCKW
* Task Setter: visitorCKW

### 解法說明
這題直觀的做法是對每一位裁判在調酒之中用線性搜索找到該位裁判會挑選的調酒，時間複雜度$O(NQ)$，時間複雜度過高。
因此這題主要是利用排序的手法加上二元搜尋樹的運用。
先將所有的調酒以及評審依照濃度由高到低做排序，並且建立一棵空的二元搜尋樹(可以使用STL的set)。
二元搜尋樹之中存的元素是調酒，樹中存所有濃度高於當前要選擇調酒的裁判的標準的調酒，並且依照調酒位置的數值做排序。
因此，每個裁判在選擇時，只要在樹中做二分搜找出距離裁判最接近的調酒即為答案。
由於每杯調酒只被加入樹中一次，並且每次加入樹中的複雜度為$O(lgN)$，因此將調酒加入樹中的總複雜度為$O(NlgN)$
另外，每位裁判會挑選一杯調酒，每次挑選都是在樹中做1次二分搜，因此複雜度也是$O(QlgQ)$。
因此，總時間複雜度為$O(NlgN+QlgQ)$。
空間複雜度則為$O(N)$。

### 標準程式
:::spoiler

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, Q;
    cin >> N >> Q;
    vector<vector<int>>arr, query;
    vector<int>ans(Q);
    for(int i = 0; i < N; i++){
        int x, y;
        cin >> x >> y;
        arr.push_back({x,y});
    }
    for(int i = 0; i < Q; i++){
        int a, b;
        cin >> a >> b;
        query.push_back({a,b,i});
    }
    sort(query.begin(), query.end(), [](const auto& q1, const auto& q2){
      return q1[1] > q2[1];
    });
    sort(arr.begin(), arr.end(), [](const auto& a1, const auto& a2) {
      return a1[1] > a2[1];
    });
    int j = 0;
    set<int> bst;
    for (const auto& q : query) {
        while (j < N && arr[j][1] >= q[1])
            bst.insert(arr[j++][0]);      
        if (bst.empty()) {
            ans[q[2]] = -1;
            continue;
        }
        const int id = q[0];
        auto it = bst.lower_bound(id);
        int id1 = (it != bst.end()) ? *it : INT_MAX;
        int id2 = id1;
        if (it != bst.begin())
            id2 = *prev(it);
        ans[q[2]] = abs(id1 - id) < abs(id2 - id) ? id1 : id2;
    }
    for(auto x : ans) cout << x << '\n';
    return 0;
}