###### tags: `BiWeekly Contest`
# BiWeekly Contest 100 (03/18)
## [2591. Distribute Money to Maximum Children](https://leetcode.com/problems/distribute-money-to-maximum-children/description/)(<font color="00b8a3">Easy</font>)

### Solution
判斷題目給出的條件
1. 每個人都至少要有1元
2. 不能有人拿到4元

限制 :
>1 <= money <= 200
>2 <= children <= 30

#### 時間複雜度 : ***O(1)***

#### 空間複雜度 : ***O(1)***

程式碼<font color="ff0000">**(改良前)**</font> :

class Solution {
public:
    int distMoney(int money, int children) {
        int ans = 0;
        money -= children;
        
        if(money < 0)   return -1;
        
        while(money >= 7){ 
            ++ans;
            money -= 7;
            if(ans == children && money)    return (children - 1);
        } // while迴圈應該可以改用數學的方法做一次就好
        
        if(money == 3 && ans && children - ans == 1)  --ans;
        
        return ans;
    }
};

程式碼<font color="ff0000">**(改良後)**</font> :

class Solution {
public:
    int distMoney(int money, int children) {
         if( money < children ) return -1;
        money = money - children;

        int ans = min(money / 7, children);
        if(ans)
        {
            if((money%7 == 3 && children - ans == 1) || money > children * 7)
            {
                ans -= 1;
            }
        }
        return ans;
    }
};

## [2592. Maximize Greatness of an Array](https://leetcode.com/problems/maximize-greatness-of-an-array/)(<font color="FFC011">Medium</font>)

### 題意
將陣列重新排列後, 陣列中的值比原陣列同樣位置的值還大的數字個數

### 限制
>1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

### Solution 1
先用unordered_map計算陣列中的每個值有多少個
排序完後放到vector中(從小到大)
再利用雙指標(two pointer)
指標A從第0個開始, 指標B從第1個開始
一一配對消除, 消除的數量加到最後的答案
當指標B指到最後的時候就輸出答案

#### 時間複雜度 : ***O(nlogn)***

#### 空間複雜度 : ***O(n)***

程式碼 :

class Solution {
public:
    int maximizeGreatness(vector<int>& nums) {
        vector<pair<int, int>> v;
        vector<pair<int, int>> v1;
        unordered_map<int, int> m;
        int index = 1;
        int ans = 0;
        for(int i : nums){
            ++m[i]; // 計算數量
        }
        for(auto& i : m){
            v.push_back({i.first, i.second});
        }
        sort(v.begin(), v.end());
        for(auto& i : v){
            v1.push_back(i);
        }
        
        // size = 1 代表只有同一種數字
        // 不管怎麼移都不會比原本大
        if(v.size() == 1)   return 0; 
        
        // i從第0開始, index從第1開始
        for(int i = 0; i < v.size(); ++i){
            while(v[i].second){
                //cout << v[i].first <<" " << v[i].second <<" : " << v1[index].first <<" " << v1[index].second << endl;
                if(v1[index].second == 0 || index == i)   index++;
                if(index >= v1.size()){
                    return ans;
                }
                int temp = min(v[i].second, v1[index].second);
                ans += temp;
                v[i].second -= temp;
                v1[index].second -= temp;
                //cout << v[i].first <<" " << v[i].second <<" : " << v1[index].first <<" " << v1[index].second <<endl << ans << endl << endl;;
            }
        }
        return ans;
    }
};

### Solution 2
用數學的方法, 計算出現最多次的值的數量
用整個vector的size減去上面求出的數量就是答案

> [1 2 2 3 3 3 5 5 7 7 7]
> 出現最多次的是3跟7, 有3次
> 如果左移的次數小於3
> 就代表有一個3會跟左移後的3重疊, 7也是
>
>
> [1 2 2 <font color="ff0000">**3**</font> 3 3 5 5 <font color="ff0000">**7**</font> 7 7] <- <font color="ff5511">**原本的**</font>
> [2 3 3 <font color="ff0000">**3**</font> 5 5 7 7 <font color="ff0000">**7**</font> 1 2] <- <font color="ff5511">**左移2次**</font>
> >算出的答案是7
> >但應該是8, 因為少算了重複的部分

用sort過的陣列比較好想, 但實際上不用sort

#### 時間複雜度 : ***O(n)***

#### 空間複雜度 : ***O(1)***

程式碼 :

class Solution {
public:
    int maximizeGreatness(vector<int>& nums) {
        unordered_map<int, int> m;
        int max_cnt = 0;
        for(int i : nums){
            ++m[i];
        }
        for(auto& i : m){
            max_cnt = max(max_cnt, i.second);
        }
        return (nums.size() - max_cnt);
    }
};

## [2593. Find Score of an Array After Marking All Elements](https://leetcode.com/problems/find-score-of-an-array-after-marking-all-elements/)(<font color="FFC011">Medium</font>)

### 題意
在陣列中尋找沒有被標記的最小值(值相同時index小優先)
將該值加入總和, 並標記該值及它左右的值
當所有值都被標記後回傳總和

### 限制
>1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6

### Solution
用unordered_map紀錄每個值所在的位置
再放入priority_queue(從小排到大)
需要建立跟nums一樣大小的陣列來確認該格是否被標記
之後從最小的值開始一個一個搜尋

#### 時間複雜度 : ***O(n^2)***

#### 空間複雜度 : ***O(n)***

程式碼 :

class Solution {
    template <typename T>
    class cmp
    {
    public:
      //重載 () 運算符
      bool operator()(T a, T b)
      {
        return a > b;
      }
    };
public:
    long long findScore(vector<int>& nums) {
        unordered_map<int, vector<int>> m; // 數字所在的index值
        vector<bool> mark(nums.size()); // 紀錄是否被標記
        priority_queue<int, vector<int>, cmp<int>> pq;
        long long ans = 0;
        int cnt = 0;
        
        for(int i = 0; i < nums.size(); ++i){
            m[nums[i]].push_back(i);
            pq.push(nums[i]);
        }
        
        while(pq.size()){
            if(cnt == mark.size())  return ans;
            int temp = pq.top();
            pq.pop();
            for(auto& i : m[temp]){
                if(!mark[i]){
                    if(i - 1 >= 0){
                        if(!mark[i - 1]){
                            ++cnt;
                        }
                        mark[i - 1] = true;
                    }
                    mark[i] = true;
                    if(i + 1 < mark.size()){
                        if(!mark[i + 1])    ++cnt;
                        mark[i + 1] = true;
                    }
                    ans += nums[i];
                    ++cnt;
                    //cout << nums[i] << " " << ans << endl;
                }
            }
        }
        return ans;
    }
};

運用類似的想法，但priority_queue裡是儲存每個元素的index與value，運用priority_queue的特性，可以在logn的時間取得值最小的元素並標記，如果取得的元素是被標記過的，便直接捨棄。如此一來，實作程式碼會簡潔很多。

#### 時間複雜度 : ***O(nlogn)***

#### 空間複雜度 : ***O(n)***

程式碼 :

class Solution {
public:
    long long findScore(vector<int>& nums) {
        int n=nums.size();
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        vector<bool> b(n);
        for(int i=0;i<n;i++){
            pq.push(make_pair(nums[i], i));
        }
        
        long long ans=0;
        while(!pq.empty()){
            int idx=pq.top().second;
            if(!b[idx]){
                ans+=pq.top().first;
                b[max(idx-1, 0)]=true;
                b[idx]=true;
                b[min(idx+1, n-1)]=true;
            }
            pq.pop();   
        }
        return ans;
    }
};

## [2594. Minimum Time to Repair Cars](https://leetcode.com/problems/minimum-time-to-repair-cars/description/)(<font color="FFC011">Medium</font>)

### 題意
找出可以洗完cars輛車的最小時間

### 限制
>1 <= ranks.length <= 10^5
1 <= ranks[i] <= 100
1 <= cars <= 10^6

### Solution
Binary Search
從 0~LLONG_MAX 中搜尋出一個時間
藉由遍歷確認能不能完成
不能的話就把時間拉長(left = mid + 1)
能的話就把時間縮短(right = mid - 1)

#### 時間複雜度 : ***O(nlogn)***

#### 空間複雜度 : ***O(1)***

程式碼 :

class Solution {
public:
    vector<int> r;
    bool check(long long mid, int cars){
        long long temp;
        for(int i : r){
            temp = mid;
            temp /= i;
            if(cars <= sqrt(temp))   return true;
            cars -= int(sqrt(temp));
        }
        return false;
    } 
    long long repairCars(vector<int>& ranks, int cars) {
        for(int i : ranks){
            r.push_back(i);
        }
        long long l = 0;
        long long r = LLONG_MAX - 1;
        long long mid;
        while(l <= r){
            // cout << l << " " << r << endl;
            mid = (l + r) / 2;
            if(check(mid, cars)){
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        return max(l, r);
    }
};

## []()(<font color="00b8a3"></font>)

### 題意

### 限制

### Solution

#### 時間複雜度 : ***O()***

#### 空間複雜度 : ***O()***

程式碼 :

FFC011
ff375f