# **_Leetcode題目題解_**

[TOC]

---

___題目來源___ :arrow_down: :arrow_down: :arrow_down:
[___leetcode for APCS 系列題___](/SLorq5XNSlKxKPf7klVxiA)

> ___喜歡程式、享受coding___

---

##### *__1. jump game__*
題目：[jump game 1](https://leetcode.com/problems/jump-game/)
使用技巧：___<font color="#f00">greedy</font>___
:::spoiler `解答`

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int reach = 0 ;
        for(int i = 0 ; i < nums.size() ; i++){
            if(reach < i) break ;
            if(reach < i + nums[i]) reach = i + nums[i] ;
        }
        return reach >= nums.size() - 1 ;
    }
};

:::

##### *__2. jump game 2__*
題目：[jump game 2](https://leetcode.com/problems/jump-game-ii/)
使用技巧：___<font color="#f00">greedy</font>___
:::spoiler `解答`

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> v(nums.size() , 1e9) ;
        v[0] = 0 ;
        for(int i = 0 ; i < nums.size() ; i++){
            for(int j = i ; j <= i + nums[i] && j < nums.size() ; j++){
                if(v[j] > v[i] + 1) v[j] = v[i] + 1 ;
            }
            if(i + nums[i] >= nums.size()) break ;
        }
        return v[nums.size() - 1] ;
    }
};

:::

##### *__3. jump game 3__*
題目：[jump game 3](https://leetcode.com/problems/jump-game-iii/)
使用技巧：___<font color="#f00">BFS</font>___
:::spoiler `解答`

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        const int maxn = arr.size() ; 
        queue<int> q ;
        vector<bool> red(maxn , 0) ;
        red[start] = 1 ;
        q.push(start) ;
        while(!q.empty()){
            int f = q.front() ;
            q.pop() ;
            if(!arr[f]) return true ;
            if(f + arr[f] < maxn && !red[f + arr[f]]){
                q.push(f + arr[f]) ;
                red[f + arr[f]] = 1 ;
            } 
            if(f - arr[f] >= 0 && !red[f - arr[f]]){
                q.push(f - arr[f]) ;
                red[f - arr[f]] = 1 ;
            } ;
        }
        return false ;
    }
};

:::

##### *__4. jump game 4__*
題目：[jump game 4](https://leetcode.com/problems/jump-game-iv/)
使用技巧：___<font color="#f00">hash_map+BFS</font>___

:::spoiler `解答`

class Solution {
public:
    int minJumps(vector<int>& arr) {
        const int maxn = arr.size() ;
        unordered_map<int , vector<int>> mp ;
        queue<int> q ;
        vector<bool> red(maxn , 0) ;
        vector<int> t(maxn , 0) ;
        for(int i = 0 ; i < maxn ; i++) mp[arr[i]].push_back(i) ; // monotonious
        q.push(0) ;
        red[0] = 1 ;
        while(!q.empty()){
            int f = q.front() ;
            q.pop() ;
            if(f == maxn - 1) return t[f] ;
            if(f + 1 < maxn && !red[f + 1]){
                q.push(f + 1) ;
                red[f + 1] = 1 ;
                t[f + 1] = t[f] + 1 ;
            }
            if(f - 1 >= 0 && !red[f - 1]){
                q.push(f - 1) ;
                red[f - 1] = 1 ;
                t[f - 1] = t[f] + 1 ;
            }
            for(auto it : mp[arr[f]]){
                if(!red[it]){
                    red[it] = 1 ;
                    t[it] = t[f] + 1 ;
                    q.push(it) ;
                }
            }
            mp[arr[f]].clear() ; // 以免重複做已經做過的事情
        }
        return -1 ;
    }
};

:::

##### *__5. jump game 5__*
題目：[jump game 5](https://leetcode.com/problems/jump-game-v/)
使用技巧：___<font color="#f00">DP+BFS</font>___

:::spoiler `解答`

class Solution {
public:
    static const int maxn = 1e3 + 5 ;
    int dp[maxn] , dis , len ; // dp record the max visit at every position
    vector<int> copy ;

    int DFS(int num){
        if(dp[num] != 0) return dp[num] ;
        int ret = 0 ;
        for(int i = num - 1 ; i >= num - dis && i >= 0 && copy[num] > copy[i] ; i--){
            ret = max(ret , DFS(i)) ;
        }
        for(int i = num + 1 ; i <= num + dis && i < len && copy[num] > copy[i] ; i++){
            ret = max(ret , DFS(i)) ;
        }    
        return dp[num] = ret + 1 ;
    }
    int maxJumps(vector<int>& arr, int d) {
        dis = d , len = arr.size() , copy = arr ;
        for(int i = 0 ; i < arr.size() ; i++) DFS(i) ;
        return *max_element(dp , dp + len) ;
    }
};

:::

---

### *__好題目選講__*

##### *__1. Factory Machines(From CSES)__*
題目：[Factory Machines](https://cses.fi/problemset/result/5873024/)
使用技巧：<font color = "#f00">*__二分搜__*</font>
:::spoiler `解答`

#include<bits/stdc++.h>
using namespace std ;
#define fastio ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define int long long
const int maxn = 2e5 + 5 ;
int arr[maxn] , n , p , t ;

bool reach(int num){
    t = 0 ;
    for(int i = 0 ; i < n ; i++) t += num / arr[i] ;
    return t >= p ;
}

signed main(){
    fastio ;
    int minn ;
    cin >> n >> p ;
    for(int i = 0 ; i < n ; i++) cin >> arr[i] ;
    minn = *min_element(arr , arr + n) ;
    int l = 1 , r = p , mid ;
    while(l <= r){
        mid = (l + r) >> 1 ;
        if(reach(minn * mid)) r = mid - 1 ;
        else l = mid + 1 ;
    }
    // 第一次二分搜，找出最少時間得可以處理幾個
    r = minn * l + minn , l = minn * l - minn ;
    
    while(l <= r){
        mid = (l + r) >> 1 ;
        if(reach(mid)) r = mid - 1 ;
        else l = mid + 1 ;
    }
    // 第二次二分搜，處理其他機器超時的問題
    cout<<l<<'\n' ;
}

:::